It sounds like the index files may have been corrupted. To try it, close down The Bat! totally, and then open up Explorer and go to your Mail folder. Find an account where you have had a problem deleting messages, and select the folder where the messages are stuck. Look for the file called messages.tbi (make sure the extension *is* .tbi and not .tbb - the .tbi is the index file, the .tbb is the message base itself.) Remove the messages.tbi file. The relaunch The Bat! and go to the folder which matches the one you have just removed the .tbi file from. The Bat! will recreate a new .tbi file for that folder by re-indexing the message base .tbb file. Then see if you can delete messages. If this works then repeat for each affected folder, making sure The Bat! is closed before you delete the .tbi files.
Note: the .tbi file also holds the record of whether messages are replied to, forwarded, etc... so you will lose that info when you delete the .tbi file, but if it solves the problem you have it's a small price to pay.
Hope this helps.