I'd suggest an Undo button/link right beside the message, similar to what gmail does when you, for example, delete an email.
I'd suggest an Undo button/link right beside the message, similar to what gmail does when you, for example, delete an email.