A system for verifying VoIP call routing information. In particular implementations, a method includes verifying one or more Voice-over-Internet-Protocol (VoIP) call agents for respective destination telephone numbers based on demonstrated knowledge of previous public switched telephone network (PSTN) calls to the respective destination telephone numbers; receiving a call initiation message identifying a destination telephone number; and conditionally initiating a call over a VoIP network to a target VoIP call agent, or over a circuit switched network, based on whether the target VoIP call agent has been verified for the destination telephone number identified in the call initiation message.