Cannot delete non un-used membership

I have two membership types of which the second membership type has recently been disabled. We removed the membership from all contacts or deleted contacts that had that membership type.

When I try to delete the membership type Civi presents me with an error box stating:

Membership Not Deleted
This membership type cannot be deleted due to following reason(s):
1. There are some contacts who have this membership type assigned to them. Search for contacts with this membership type on the CiviMember >> Find Members page. If you delete all memberships of this type, you will then be able to delete the membership type on this page. To delete the membership type, all memberships of this type should be deleted.

When I do a find members or advanced find for the membership type I get the following:

No matches found for:
Membership Type = Affiliate ...AND...
Membership Status = Grace

Suggestions:
if you are searching by member name, check your spelling
try a different spelling or use fewer letters
if you are searching within a date range, try a wider range of values
make sure you have enough privileges in the access control system