VBA can do this:

The first is an event module for your worksheet, the second needs to go
into a standard code module.

Private Sub Workbook_SheetChange(ByVal Sh As Object, ByVal Target As
Range)
' adaptation of http://www.j-walk.com/ss/excel/tips/tip98.htm but
works for whole workbook
' and works with different types of validation
' Does the validation range still have validation?
' requires sheet level ValidationRange for each sheet seperatly
(that has validation)
' All ranges that have been set seperatly with Data Validation
needs to be unioned
' seperatly.
' e.g. if A2:A20 and B2:B20 both have their own validation,
ValidationRange = A2:A20,B2:B20.
Dim rngVal As Range

On Error GoTo err

If Not Sh.ProtectionMode And Sh.ProtectContents Then
Sh.Protect "", , , , True
End If

On Error Resume Next
Set rngVal = Sh.Range("ValidationRange")
If err.Number < 0 Then Exit Sub
On Error GoTo err


If HasValidation(rngVal) Then
Exit Sub
Else
Application.EnableEvents = False
Application.Undo
MsgBox "Your last operation was canceled." & _
"It would have deleted data validation rules.", vbCritical
Application.EnableEvents = True
End If

Exit Sub
err:
MsgBox err.Description, , err.Source, err.HelpContext,
err.HelpContext
End Sub

Public Function HasValidation(r As Range) As Boolean
' needs to be in code module
' Returns True if every cell in Range r uses Data Validation
' The validation.type will raise an error when de range contains
validations that where not set
' in one action (even if the type is the same). We assume the range to
be split per validation set

Dim rngarea As Range
Dim x As Integer

On Error Resume Next
HasValidation = True
For Each rngarea In r.Areas
x = rngarea.Validation.Type
If err.Number < 0 Then
HasValidation = False
Exit For
End If
Next rngarea
End Function\

DM Unseen