There is not a way to delete multiple contacts in the address book. If you are syncing to Outlook, delete them in there and then connect the device and sync.
Just re-read your post. If you want to delete all of the contacts, you can run the Desktop Manager on your pc, connect the device and select Backup and Restore > Advanced and in the right hand list select "address" and below the list click Clear.