I had Vista hitting up Exchange 2k no problem...
Are there any other symptoms?
You getting any other error messages?
Can it see the Exchange server? Is this over a VPN connection? Firewall lameness?
Is his W7Ultimate x64?
Is OWA available (I imagine he is like the NOES on that, but it's an option).
Server 2000 extended support ends 7/13 this year...
If they are just tightwads, see if they would go for Kerio... it's very nice.
Just for shats and gaggles, try connecting him to a test account on that server... see if it is a profile thing...
For the printer, can you add it as a device mapped through the host OS? Through the Virtual PC menu inside the XP VM...
Also, can you attach to the printer directly over the network... probably need to static IP the thing...