I think that strikeiron's ZIP code service does this. It's free for the first 250 hits or so.
The data you want doesn't fall from trees; it must be collected, updated, and corrected and formated, and providing the service online requires servers, bandwidth, maintenance, and development. I'm not sure you'll find what you're asking for without a payment.
The cheapest route might be to purchase a ZIP code list and build the database yourself.