Compression?

I don't know that such a lookup is terribly expensive at all.  If someone shows up with
options that aren't in your "greatest hits" list, you don't need to update anything until the
person makes a complete connection.

Initially, syncookies don't even get engaged at all anyway.  Once they do get engaged, all
you're left with is a table lookup to find hit/miss in the greatest hits table, and a version
of the existing cryptographic hash if the pattern's a miss.  With a properly designed
(non-cryptographic) hash for the "greatest hits" lookup, that should go very quickly and
cheaply, and can even save you from doing the cryptographic hash for the syncookie.  You could
actually end up ahead of the curve in terms of computational load.