I think i know what may be causing the problem - though it's a bit of an educated guess....

Are the external lines analogue?

I suspect the analogue lines are taking time to clear down (in the UK we need to adjust network CPC timers). As a result, the VM still thinks a call is connected to the mailbox.

I believe the VM can only route a single call to a mailbox at a time.

Therefore call recording cannot be made at this time as the mailbox is seen to be in use.

Program up some DT keys to see of trunks are remaining open.
Test my theory by making a call to a phone forwarded to VM whislt leaving a message on another extn.
Monitor the VM see if the port is clearing down.

Hope this helps