In many cases the best message is no message ;)
Is there the expectation of success? In these cases the only time a user wants to see a message is when something's gone wrong. Take file deletion in Windows. After the "Are you sure?" question has been answered there's no further message unless the file couldn't be deleted for some reason.
Is there any other feedback that the record has been deleted? Taking Windows as an example again, the user can see that the file has been deleted as it no longer appears in the file explorer.
Does the delete operation take a long time? If you're deleting something from a remote database there may be some time from when the delete request is issued and when the delete actually occurs. There's also a disconnection from the action and the result as the delete is asynchronous. In this case you probably do want a message.
As to what that message should be, any of the ones you list are OK. However, you might want to drop the "successfully" as that raises the possibility of failure in the user's mind. The simple:
The [record] was deleted.
where [record] is the name of what you are deleting is probably all you need.