Sounds like you've implemented a type of JWT: http://openid.net/specs/draft-jones-json-web-token-07.html
"Our backend checks if a query is legit by computing all the possible hashes using all your available API keys"
So why not just forget about the crypto (with all the risks of getting it wrong) and use an opaque bearer token?
I guess it's a question of where do you store application state - do it at the server and then you have to replicate the database that stores that state. Store session state at the client and pass it to the server means you can go to any data center at the potential risk of getting the security wrong.