Same here. I added the www -> non www 301 for Google in the hopes of fixing canonical problems, not too long after that Yahoo and MSN started listing my main page with the www!
I've tested headers at 5 or more places, looked at the log files and it is sending a 301.
I've now fallen out of the serp for my main pages on all the big engines. Before the 301 I didn't notice MSN or Yahoo having a problem with knowing my url is without the www and I'd been ranking fine.
I also was using outbound tracking on my links using a 301. Yahoo has listed many of those outbound urls in site: but with the targets title, not the link text I used to link to them!
Targets Sites Page Title
I know 100% that the outbounds were always 301, those were tested and checked in the log files as well.
The odd thing I've noticed is that with both MSN and Yahoo, my main page seems to be the only one that has the www added, inner pages (*knock on wood*) remain without.