There are two parts to this answer.
First: in order to do what you want, you will need to implement a VBA macro or .COM addin. You will need to hook your code to the event ProjectBeforeTaskDelete which is available from Project 2000 onwards. For help in writing this code, you should ask further questions in the VBA forum.
Your proposed solution, however, has a difficulty you need to overcome. Quite simply: how do you know which tasks cannot be deleted? Let's assume that you indicate these tasks by putting the text "mandatory" in the Text1 field. Your VBA routine is invoked whenever the delete key is pressed and checks the field. If the field says "mandatory" then your routine displays an error message and cancels the delete.
Very quickly, your staff will realize that they can circumvent your protection by removing the word "mandatory" from Text1. To prevent that you will have to check every time a field is changed to see if Text1 is being changed from "mandatory" to something else. This adds additional complexity and processing.
Finally, what happens when you migrate to Project Enterprise? These fields can be changed in PWA so you need to put the same tests there -- and that is definitely a non-trivial effort.
Second: I would not do what you are doing. Instead, I would simply create a standard project template that has mandatory tasks in red. PMs would be instructed that red tasks are never to be deleted. When your PMO performs its regular project plan reviews (you do review all active plans at least every month, don't you) the PMO staff would do a quick check of the red tasks and, if any were missing, the PMO would apply appropriate disciplinary action.
I know: it's not a high tech solution. But I also know: my approach works (that's what we did and it was successful at accomplishing your stated goal).
