You should definitely post this on the Unified Applications Forum (Unity) so more experts there can have a look at this question :) I think most would recommend skipping 4.0(4) for sure and at minimum going with 4.0(5). That being said, if you are going to upgrade then why not go to 4.2(1)?
Here is some Upgrade documentation;
Upgrading Cisco Unity 4.x Software to the Shipping Version
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...