If the message box is a must, you need the normal means of deleting the cell contents to initiate it.
As ArviLaanemets says, the Change event firing every time something changes will slow down your worksheet
but depending on the worksheet that may or may not be an issue.
Put this code into the sheet module and give it a try.
Code:
Private Sub Worksheet_Change(ByVal Target As Range)
Dim aCell As Range
For Each aCell In Target.Cells
If aCell.Value = "" Then
If MsgBox("Are you sure you want to " & _
"delete cell contents ?", 36, "DELETE CELLS ?") <> vbYes Then
Application.EnableEvents = False
Application.Undo
Application.EnableEvents = True
End If
End If
Exit For
Next aCell
End Sub