Sorry for the late reply all. I'm currently at MozCon and the Wifi is horrible - also if anyone is here let me know :)
Cferto, we still haven't started this project just yet. In order to redirect on the page level we have to change our IA and figure out what we want our new URL structure to be. This is going to be a lot to undertake so you can imagine management is moving very slow on this project. I do agree that redirecting page by page is the best way to go about it (at least that is what all my research has shown).
@planet13 thanks for posting that video. It makes sense that Google would treat those redirects as 404's. I still haven't had a chance to watch the full video but definitely checked it out at the marker that you sent.
@sbook - not sure about that one. I'm assuming it would not be good for that new domain, anyone want to chime in on this?