In version 2003 had clicked on Contacts and created new address folders
under Contacts.
Then at a later time had gone into Contacts and deleted folders.
Now when in Contacts folders are gone.
However they are not gone in the address book.
Open the address book and the 'show names from the: " drop down still shows
all the now gone folders.
In my case it lists:

Outlook Address Book
Contacts
Contributers
Contributers
Sub1
Subs
Subs
Subscribers

All folders are actually deleted except for Contacts itself.
Clicking one of these in the list gets me the dialog-
The address list could not be displayed. The contacts folder associated with
this address list could not be opened; it may have been moved or deleted
(whoa what a smart error message!! ;-)  or you do not have permissions. For
more information on how to remove this folder from the Outlook Address Book,
see MS Office Outlook Help.

Well I got diddly squat from Help and have been hunting high and low for a
way to delete the deleted.

I guess one has to be Indiana Jones to figure it out?