permanent 404's don't seem to affect Yahoo and MSN, I suppose they just drop them. But googlebot cache control is different, it will keep coming and asking but it won't crawl past that 404.
This causes uncrawled pages to lose the description leaving URL only. And I'm not sure why but some other related? pages will not lose their description but they will go supplemental.
also helleboirne said
Use a server header checker and see what you get requesting the different versions of a page.
If it is a 302 then you need a different host.
I'm using a virtual host and I do get a 302 on the non-www version of my site. But they use cgi's and 'actual location' of my site is not www.mysite . it works fine for me though, they must be blocking robots from following the 302 on my host. But your host may not be.
I have .htaccess too (but not to 301 www vs non-www)