The short answer is yes. Really any mailbox can reside on any Exchange server as long as they are in the same organization as the Exchange partner server. Without more details, that would be my answer on that.
Thanks for the response, just to clarify, we are migrating from exchange 2003 to 2007, we have moved all the user mailboxes of the current server and voicemail is still working ok after running the permissions wizard. We will be migrating the partner server also to 2007 but not yet, the example administrator account is still on the old 2003 message store, so we should be ok to just move this account like we have done with the end user accounts ?
Yes but I would partner with the 2007 Exchange soon after since all your mailboxes will be there at that point.