I have tried the contact2sim program, and the free version doesn't delete contacts off sim. It goes through the action, but contacts remain.
I found a very simple way that should work on most phones, but this description is specific to HTC Desire.
1. Go to People program (contact list)
2. Press menu button, and select view
3. Tick/select only sim contacts, then select done
4. Press menu button again, and select delete. A list of all sim contacts should appear.
5. At this point you can select individual contacts to delete, or by pressing menu again, you will have option to select all
6. Press delete, and sim contacts will be gone.
Good luck