When you delete an NDS account this doesn't delete the GroupWise account unless you push the Radio Button to delete the mail account. So the mailbox may still be there, you will have to try to open the mailbox with a GW Client using the users login name to see if it is OK! If that works you can find the three digits that are used as the FID by the databases. The databases are usually USERXXX.db where the XXX is the FID # like AA2 or something similar. If the mailbox was deleted you have no way of knowing what the old FID for your user was as the new account has a different FID # now, thats why the mailbox was empty. So if you have say 500 mailboxes backed up on tape you will have to match 499 with your current users and the last one will be your deleted user. Do you see what the problem is going to be to get the users mail back, the FID is the key to the whole thing. There are a lot of Tid's on the Novell Support Site about this subject so do some searching for them.
Good Luck
Ken