This paper presents a scalable mechanism, Fast Routing Table Recovery (FRTR), for detecting and correcting route inconsistencies between neighboring BGP routers. The large size of today's global routing table makes the conventional periodic update approach, used by most routing protocols, infeasible. FRTR lets neighboring routers periodically exchange Bloom filter digests of their routing state. The digest exchanges not only enable the detection of potential inconsistencies during normal operations, but also speed up recovery after a BGP session reset. FRTR achieves low bandwidth overhead by using small digests, and it achieves strong consistency by "salting" the digests with random seeds to remove false-positives. Our analysis and simulation results show that, with one round of message exchanges, FRTR can detect and recover over 91% of random errors that the current BGP would have missed with an overhead as low as 1.3% of a full routing table exchange. With salted digests FRTR can detect and recover all the errors with a probability close to 100% after a few rounds of message exchanges.