There are some Vista-specific issues with relation to MinGW. The solution involves installing patched versions of gcc.exe and g++.exe. Grab
http://dessent.net/tmp/gcc-vista-3.4.5-20060117-1.tar.gz and unpack it in your MinGW root folder (ie Data/MinGW). It should install the patched files in all the right places.
The fact that you found it necessary to add libexec\gcc\mingw32\3.4.5 to the path is consistent with this "Vista-specific" issue ... as also is the inability to locate the header files.
However, if you were running perl 5.8 on Vista against this same version of MinGW, then you should have struck exactly the same problem ... but you didn't. (I'm guessing you *weren't* running 5.8 on Vista using the same version of MinGW).
Having installed the patched files you can then remove those 3 folders that you quoted from the path.
Cheers,
Rob