The answer to both questions is yes. You could either upgrade the current system and then move to the new box or move 3.x to the new box and then upgrade. I would recommend that you upgrade first and then move so that you have a clean installation of 4.0(5) and Exchange 2000 on the new server. Take a look at the Reconfiguration and Upgrade Guide below. There are sections on upgrading Unity, upgrading Exchange, and moving to a new server.
According to the following link, Exchange 5.5 is supported when upgrading from 3.x. The previous link is referring to the fact that Exchange 5.5 is not supported for use with Unity 4.2(1). So, I would recommend a phased approach to the migration.
1. Upgrade Unity on the current server to 4.0(5).
2. Upgrade Exchange on the current server to 2000.
3. Move the installation to the new hardware on which you have installed Unity 4.0(5) and Exchange 2000.
I'm not able to access my old voice mail messages all of a sudden. The recording says something like 'the message is currently not available'. This has never happened before in all the years I have been using this system. I have t...