I will try and help below - but as long as the appointments don't have notes etc then they are unlikely to be taking up much room

I also find it useful to have past appointments on my iPaq I as frequently want to check when past discussions occurred (ie it acts as my past diary as well my future diary).
I am also assuming that the appointments you are trying to delete are not recurring appointments - as even with your settings ALL occurrances of recurring appointments will remain.
What I would do is (make a back-up of you desktop Appointments first - I have never tried what I am going to suggest so just in case - to do this in Desktop Outlook got to File>Import and Export>Export>Export to a file> choose .pst and export your appointments).
In AS change it to PC overwrites the device and also sync 1 past week and all future. Then on your device delete all past appointments. Then sync.
Does that work?
If not. Change the settings in AS to Sync all items (leave the 1 past week and all future the same). In desktop Outlook delete all past appoinmtments (don't worry as 1) they will be in your deleted items folder and 2) you have the back-up). Now sync.
Does that delete the items from your iPaq? if not - now delete them from your iPaq. resync. They should now be gone.
Go to the deleted items in Outlook and recover the appointments deleted - they should not sync back to your ipaq.
Long winded I know - but I tried to do it on an easiest option first basis.