My secret sauce has been Adobe Media Encoder. It really churns out some amazing stuff when you're trying to encode for the web or DVD - and although I've used it for Blu-Rays before, they've not been in a very stressful environment (i.e. all I had to do was fit a 30 minute short on a Blu-Ray - at that point you can just max everything out.)
What's incredible about AME is that you can go straight from a Premiere project and do encodes from the project and you don't have t lock up Premiere. I also simply export a QT reference from either FCP or Avid and feed it to AME and it churns out great results as well.
YouTube compression is a bit more complex than Vimeo - because YouTube makes a habit of playing 1080p video, while vimeo limits you to 720p unless you're a "pro" subscriber. Most people's computers can't even handle 1080p, though, so it's debatable weather it's even a good idea to go to 1080p. If you're super picky on quality, uploading a 720p master to Vimeo and 1080p master to YouTube will give you less resizing issues.
My solution for encoding gamma issues has been to simply encode on a PC. It staves off Gamma issues and (again) by using AME on a PC, I'm able to fully utilize 64 bit and multiple, hyper-threaded cores for rendering as fast as possible. There was a Cow article recently about this: http://magazine.creativecow.net/arti...s-opened-doors.
I don't claim to know how YT and Vimeo's encoding works, but I have found that if I have rock-solid h.264 encoding it will translate to no discernible difference when re-encoded into YouTube or Vimeo. They use h.264, so perhaps it's just a pass-though situation. When using Adobe Media Encoder, it's important to use the h.264 setting, and NOT the QuickTime-wrapped h.264 setting. This produces an M4V, but it's still the same thing - readable by the same programs, same encoding, same data - but the AME options are MUCh more robust for the h.264 encoder.