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. If there's no other feedback then a "success" message might be appropriate.
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.
[record] is the name of what you are deleting is probably all you need.
Additionally the message should probably disappear automatically after a few seconds so the user doesn't have to dismiss it themselves - unless they want to. The only caveat I'd add here is that if the disconnect between the requesting the delete and the delete being reported back to the user is large then leaving the message around might well be a good thing as the user might not notice it when it first appears.