Searching for `() {' _should_ (and I'm happy to be corrected here) find most attempts at exploiting, since that's the key sequence that triggers bash's "parse this environment variable as a function" behaviour.
If you look at the bash source code, the relevant parsing function checks if an environment variable begins with the literal 4-character string of "() {". That's why it's pretty easy to detect exploits: you can't do anything to evade a filter checking for this in an HTTP header. An HTTP server should not be doing any decoding of an HTTP header that could result in "() {" being obfuscated. This may not apply for attacks against things that aren't web apps, though.
Unless the input is decoded in some way before reaching an environment variable. E.g. HTML entities, hex escapes (percent or backslash), gzip, ... Best just to patch bash and switch to a different /bin/sh.
I would worry similarly about some mail headers being helpfully reassembled, then handed to procmail in environment variables.
I've got lots of wget commands in there like guylhem noted, attempting to either drop a script (and clean up) or phone home to normal random websites that were unfortunately compromised. The phone home requests have all sorts of URIs containing things from my hostnames to unique IDs.