Sounds like the search on Google Maps. This zip and street gets my block: "18411 carnation" I'd be tempted to just use Google Maps. They have APIs and easy "mash up" integration.
I'm not sure about the "without database" requirement. That probably makes it pretty near impossible.
You can purchase products that wrap a database from the US Postal Service that knows every deliverable address in the country. We use them to "standardize" addresses before mailing. Send enough mail and it saves millions on postage.
Lucene will indeed search an index, but you have to build the index. You'd need that list of all deliverable addresses to build it.