Fast encrypt, slow decrypt method for NDB Datastore
It sounds like conventional cryptographical methods should meet your needs, e.g. AES256. When it comes to crypto you should try to innovate as little as possible. Use well-established and well-trusted methods -- when "rolling your own" it's very easy to make mistakes, and you don't get the benefit of peer review from the academic cryptography community.
Make sure to benchmark how long the encryption with the strong algorithm of your choice actually takes before doing work to address the issue of the encryption blocking the request. Would a few hundred milliseconds' delay really be a problem?
If it turns out encryption is too slow, you still shouldn't compromise on the quality of your encryption algorithm. A better solution to this would be to perform the encryption in a background thread and continue with the request immediately.
Allot an ID in your database to the resource that is to be inserted in encrypted form, but don't bother with an intermediate, intentionally "mild" form of encryption before the "real" encryption. This layer would only be providing a false sense of security.
If a user attempts to access a resource that has not yet been encrypted, return an error indicating that the resource is still being processed (or that the encryption has failed, if applicable).
Make sure that there's no possibility of the encryption process failing or being delayed in a way that results in unencrypted data being kept around for longer than it should. If encryption can't succeed in a timely manner (because of disks being full / power failure / cosmic rays), the insertion must simply be allowed to fail and the unencrypted data must not be kept.
I have unencrypted web request data (not under my jurisdiction) that I would like to quickly save into the Datastore so as not to slow down the request process.
The sensitive data occasionally is required to be opened by system users via the web. When a user makes such a request, it will require them to complete a reCAPTCHA before the decryption process starts and an event is logged regarding their behavior. Decryption time could suitably be up to 1 minute long for a string of between 10 and 20 characters.
Is there an encryption algorithm usable on GAE which is slower to decrypt than encrypt that would be suitable in this case?
I'm contemplating another method to alleviate the encryption time:

temporarily store the data mildly encrypted with MD5 & hash quick encryption method, while a scheduled job iterates over any records not flagged as properly encrypted and economically applies very strong encryption (it would be acceptable for the user to be alerted that encryption has not yet finished if they tried to access the data immediately after input) 

Assuming the above method is feasible, then I assume I can encrypt the pants out of the data for a few minutes, rendering it extremely costly to try to decrypt if data is compromised but system is not.