It is weird that you couldn't delete the messages after that; I was in the same situation as you and it perfectly worked for me. Actually, the DB update has nothing to do with being able to delete posts or not... maybe you haven't updated all files when replacing the files with most up-to-date version. Hard to tell.
Well, I don't really know the WHY of things, I just know the WHAT by looking at the code. You are right: in order to fully delete a message from the database you have to delete it from both inboxes (the from and the to). Actually, the first one in deleting it just hides it from their own inbox, rather than deleting it, so that the one who still hasn't deleted it yet is still able to see it. Once that other user deletes the message it gets actually deleted from the database.
Now, I think it makes sense. I mean, I understand you'd like it to be simpler, something like: the first user in deleting the message actually deletes it from the DB. The issue with this approach is that the first user in deleting the message is "controlling" the other users' inbox by deleting a message there. It is like sending an email to a user, then regretting, deleting the message from your sent items, and then expecting it to be deleted from the recipient's inbox. If this was a democracy, I would vote for this to be the way it is right now :)
By the way, it has nothing to do with the hosting service, this is by design. Anyway, I don't know if core developers will make changes to this in the future. If you have a better approach you could post it to the v1.7 requests... but with 100 answers I hardly believe it will be herd :(