I have come across wierd hair scratching problems and this is one of them. Turns out, if there is an underscore in your domain/sub domain name, IE stops saving cookies. Which i have already mentioned in my earlier post title 'IE Why? Why?'.
Now another issue that I have noticed with underscore in domain is that PayPal will not accept this url as a valid url. So if your site has PayPal processing then it will error out.
All the fun with having underscore in domain names.