Hi there
Good move on getting the second server approved. Any other way woud be to messy.
Setting up a w2k3 server as a seconday mail and dns server is very easy. Have you thought of what mail program you would want to use? We use Smarter Mail for ours, and it really easy to use and configure, costing is good too. I think that you should get a server with at least 4 IP's. That way you can set up the MX on a seperate IP than the DNS, and give you two for future endevours.
As for getting a dedicated server, i would totally recomend Liquid Web. I can not say a bad thing about them.
http://www.liquidweb.com/
If you where after a VPS, not being able to advertise our own services

(sorry moderators!), i think Ultima Hosts would be a good choice.
Hope this helps!
Cheers
Hugh