An address matching system that maintains a central database of valid addresses has been designed. According to the invention, address matching requests are received by the system from a plurality of remote users located at respective machines (“clients”). Those requests are processed at the central system, and the results are returned to the client that made the request. In addition, novel techniques are implemented for improving the likelihood of obtaining one or more matches from a request.