#Python, 651285 bytes

*The regex to end all regexes. One final hurrah into the night.*

bzip2'd and base64-encoded version on Pastebin: http://pastebin.com/x3Vpj9zs (Pastebin didn't want the raw version because it was too big)

The key is still a nice comfortable 256 bytes.

<sub>Well, actually, I can still crank the difficulty up, assuming someone doesn't just instantly solve the smaller problems...but I wager people will have trouble with a 1GB regex...</sub>