No address marked as Primary
Thanks for the additional explanation!  One approach you could try is to use Search Builder (Search > Search Builder) and search for contacts whose primary street address is null but whose street address of your default location type (e.g., Main or Home) is not null.  If that doesn't yield the results you want, then you could search for your other location types as well (e.g., where primary street address is null and (Location Type A street address is not null or Location Type B street address is not null or Location Type C street address is not null)).