In the “oh my, how did that slip through?” category comes this one: in Dynamics CRM 2011, the ZIP/Postal Code field on the Address (CustomerAddress) entity is not searchable by default.
Weirder is that the ZIP/Postal Code fields on the Account, Lead, and Contact entities are searchable by default. Weird only because they use the same underlying table (CustomerAddress).
Keep this in mind when you wonder why you can’t search for additional addresses by ZIP code. Make that ZIP/Postal Code field on the Address entity searchable, and you’re good to go.