Some commercial zipcode databases include longitude and lattitude. If you get your hands on one of these, you'll want to preprocess it build a short list of closest zipcodes for each zipcode.

For what (little) research I did on this a few years back, is seems that using a partial match on the zipcode is a good, but not perfect, heuristic for finding close zipcodes. Were I to do this now, I'd use longitude and lattitude to map zipcodes to "hash" zipcodes into a grid that holds an array of zipcode entries. Then you can limit the search to that grid cell plus nearby adjoining grid cells.