I have a similar need for memcached, but I'm still using DO. I'm running the $5 instances running Twitter's fatcache. For $250/month, I can cheaply get 1TB of memcached storage online and available in our cluster (out of NY2).

Thrown in a some consistent hashing and I can scale up/down as needed. Fatcache is completely kick ass.