Interesting read, thanks for posting, but I think you can do better. I've been playing with Fastly and VCL recently and you could write your whole app in VCL and have it served right from the CDN. 25 million requests would cost about $20 for that. If you include the API keys in the log output and batch-process that each day/hour/whatever to keep usage stats, that would remove the need for Dynamo? You'd then keep a table of banned API keys and update that through the Fastly API dynamically.
Just a thought. Still, $150 p/m is not bad!