Clear Contacts is a freeware application for Windows Mobile 5.0 based Pocket PC and Smartphone devices that allows you to delete all contacts in one go from the address book without hard resetting/formatting the mobile device or deleting them manually one by one.

Download here
(Requires Microsoft .NET Compact Framework 2.0)