You would have a third table laid out a bit like this:
id | zip | companyID
----+-------+-----------
1 |xxxxx | 673
2 |xxxxx | 673
3 |xxxxx | 512
4 |xxxxx | 429
The first column is a unique identifying field, the second contains the zip code and the third is the company id (which is the company id used in the Companies table). For each zip code which you want to associate with a company, you would use a new row in this new table, specifying the zip code and the company id. Only the first column of this table is unique, so you can duplicate the company id as many times as required.
Your query can then perform a search on this new table without wildcards (which is quicker and less memory intensive) and join in the rest of the information from the other two tables as it needs:
SELECT * FROM Companies, Zips, CompanyZips WHERE CompanyZips.companyID = Companies.id AND CompanyZips.zip = Zips.ZipCode AND CompanyZips.zip = '$zip'
There is more information on joining 3 tables in MySQL at http://www.wellho.net/solutions/mysql-left-joins-to-link-three-or-more-tables.html