I kinda doubt that Facebook actually deletes, as opposed to setting a DB flag... weren't they caught logging comments that were typed in but then modified / deleted / not actually posted?

The other party, i.e. the recipient still has an copy, so it could be a DB flag indeed. Although when both persons delete the message it might still lay around for who knows how long.