Acejavelin,
Sorry to hear it didn't go too smooth and it is a little late now to change this, but go in and look at what compression the Voice Processor is set to. We normally keep all of ours on the G.726 (32 kbps) and I rarely have any issues with the recordings. If the System changes it when it goes to a PS-1 then you may only need to change the compression there to fix the bad audio issues.
Of course it is too late now since they rerecorded everything, but it may be valuable information for future conversions. As for the bad mailboxes I have run into that as well and the only solution I found was to delete and recreate them just as you have done.
The big question is did it fix their original problem.
Thanks,
TE