You can use Unity Voicemail only with Exchange 2007, but Exchange 2007 must be a separate box. So if you are doing this, you might as well just use Exchange 2003 for your backend and keep it all on one unity server.

For Exchange, the Mail Store Wizard gives instructions on what to do with Exchange 2007. There is a powershell script that gets created during the Unity install. You copy this to Exchange and run the script. Delegate the correct permissions, etc and you are set to go. There is documentation on Cisco's site to integrate with 2007 and Unity 5.x (4.x is not supported)