From the very limited documentation available without signing up, that service requires a roundtrip to apilimit.com's servers before fulfilling the request (to answer the "should the API do this or block this?" question). That's going to add a pretty big overhead to every request, not to mention requiring either a continuously open connection to apilimit.com or building a connection for every request, and as we're talking about customers that are hitting rate limits, that's automatically going to be a lot of requests.
A solution would be to include an encrypted token on each request that the user sends with their next request. The token would include details of how long the API should wait before fulfilling the request (or just block it the request). This would require every API server in the network being able to decrypt requests from any other server, which is a problem, but securely sharing keys can be done. It'd also be necessary for all the servers to share information about who has a token otherwise clients could just request a new token (effectively starting over). If you're willing to accept the first call being slow then that's not really a problem though.
