Stop Deleting Formula Cells Without Worksheet Protection

I'm protecting a spreadsheet with Excel 2000. For that i used the Excel functionality : Data -> " Validation"

Unfortunately, I can not protect the all sheet or workbook (Requirement). So even if the cells are protected by "Validation", any user can delete the cells using the key DELETE or BACKSPACE on the keyboard !

VBA Macro (which could be activate at each change on the sheet for example...) ? or if it's possible to avoid cells deleting with the "Validation" in the Excel Data menu ?

If it's a macro, it would do :

1 ) see if a user is pushing DELETE or BACKSPACE on the keyboard

2 ) see if the cell contains formulas

3 ) if yes, make a box appears to say that is not possible to delete this cell

4 ) return on the Excel sheet without changes