|This isn't perfect, but it's a start...|
Select the range of cells that the users will be editing (in my example, I use A1:A5).
Format...Cells...Protection tab...remove the Locked checkmark
Protect the worksheet
Paste this code into the ThisWorkbook module of the VBA editor.
Private Sub Workbook_BeforeSave(ByVal SaveAsUI As Boolean, Cancel As Boolean)
For Each cell In Range("A1:A5")
If cell <> "" Then cell.Locked = True
The user will be able to edit the cells in the range until he saves the workbook. When he saves the workbook, the code will unprotect the sheet, lock the cells within the specified range that contain data and then re-protect the sheet.
Obviously this should be made more robust by using a password (which must be included in the code), choosing the correct options in the Protection dialog box, etc. You should also password protect the VBA code so users can't change it. Macros also have to be enabled on the user's machine or it won't work.
As you can see, it can be done, but it gets complicated when you try to make it idiot - er, I mean, user-proof.