I have sent a test-message from a test-admin to a test-user and replied it from there back to the admin. All worked fine including the "new message"-alert in the users account (where this function was activated).
But then I could only delete the test message that was sent from the admin-account. I could not delete the reply-inbox-message from the admin-account nor could I delete both (outbox and inbox) in the users-account, though in all cases "message deleted" was shown. So only the one message is deleted, the others remain in their boxes, I have tried it several times in both accounts, every time it tells me that the messages are deleted, but they stay there. Very strange ...
Maybe you could get into that?
BTW, on the server is running PHP 4.4.8, according to the output of phpinfo.