Hi,
You have to protect the sheet.
Unlock all cells you want users to access, including cells with data
validation. (Format, Cells, Protection)
Then protect the sheet (Tools, Protect Sheet)
Users can now enter data, but can't change the data validation.

However, a user can still paste non-valid data into a data-validated cell,
which is really annoying. Also, when any value is pasted in this way, the
data validation is removed, despite the sheet being protected. What was MS
thinking!?

You need to use an event macro to prevent paste-happy users from wrecking
your sheet.
Regards - Dave.