Cache random results?
You could make an argument that caching all the possible combinations would be unreasonable for what's likely a low cost setup. However, I'd argue in favor of caching with both a popular and a simple reduction scheme.
Could speed it up radically by just caching on the first letter / number.