I don't know what to suggest. What you're describing seems impossible.
This getCollection() call will only get messages for the current user:
$modx->getCollection('modUserMessage', array('recipient' => $uid));
The result is used to create the checkboxes in the form, so there will only be checkboxes for messages sent to the current user.
As a result, $_POST['messages'] can only contain IDs for messages for the current user that are checked in the form, and looping through them with getObject() and remove() will only get and remove one message per iteration, so it can't possibly remove messages that are not shown in the form or are not checked.
FYI, I'm working on an extra to do this, though it may be a while before it's released.