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.
You do realize that would very quickly cause your average to increase, right? Then your average would reach a fairly stable value where practically every packet was being made to wait. But there might be occasional jumps in the average over time from unusually slow-to-process packets, which would
1. slow down all subsequent packet transmission
2. alert an attacker that the packet they just sent was statistically more likely to be of a slower-to-process variety
So depending on what you're working on, I think this might or might not be a better approach.
EDIT:
I think I might have a way to subvert your scheme.
1. Operate a server with specs identical to yours running software identical to yours.
2. Send invalid packets to both my server and your server. Figure the average difference in packet return times and factor that in to subsequent calculations.
3. Very gradually begin executing identical denial-of-service attacks on both my server and your server. The idea is to clog both your CPU and mine in the same way. As I do this, I continue sending both my server and your server authentication packets. However, my server will be configured to always treat the packets' first byte as invalid. Both of our servers' average time-to-process will gradually rise, but yours will rise differently because sometimes a packet's first byte will be correct and therefore take longer to process.
4... Once I think I've got the first byte, I can configure my server to always treat the first byte it gets as valid and begin figuring out the second byte. Etc.
Steps 1 and 2 would be much smoother if I was able to purchase a virtual server in the same cloud datacenter you were in. But hey, I'm told the cloud has some pretty big security issues to begin with, so no big deal, right?