I believe wordpress is not the right platform for matchmaking states (as well as car dealer and real estate sites). Especially when you have some essential amount of database records. It's gonna be slow, even with caching and all the regular stuff. And once your requirements grow, you're gonna realize it's not much flexible either. I'd advice looking for non-WP solutions, there are lots of them around.