It seems to me that your system has to be able to adapt to situations where the typical response time changes drastically, and the attacker can exploit discrepancies in the way the typical response time will change depending on whether a packet's nth byte is valid or not. It might be possible to make keys arbitrarily difficult to crack using methods like what you and joe_the_user suggest, but the more security you add in the form of padding on extra response time, the more your regular users will suffer.

And I agree it's difficult to keep the balance between an acceptable user experience and keeping the crackers at bay.

Instead of the comparison that checks the whole field, start two threads, one per real cpu core, and run the unknown comparison against an a known good, and in parallel, and only return when both have completed. Not the most efficient, but would scale properly for faster and slower cpus.