A method for telephony includes receiving at a facility of a telephone service provider a first subscriber request to place a first call to a specified telephone number. A provider request is sent to a remote server (26), which maintains a database (28) of records associating telephone numbers with respective packet network addresses, for a record (72) indicating a packet network address to which calls to the specified telephone number should be placed. Upon receiving the record from the remote server, the record is stored in a local cache (42) at the facility of the telephone service provider. After storing the record, upon receiving at the facility of the telephone service provider a second subscriber request to place a second call to the specified telephone number, the record is read from the local cache and is used in placing the second call to the packet network address.