There's AOL search data available at mirror sites:
http://www.gregsadetsky.com/aol-data/
There are about 20 million queries from about 650,000 users over 3 months. That's a good sized data set.
Needless to say, the brass at AOL are pretty miffed about this, and the original posting has been taken down. But there are lots of mirrors now, so it's out there for good.
Lesson Learned: If you don't want information out there, make sure it never gets onto the Internet in the first place.
Now if only Google would make their information available for everyone :)
Cheers,
Ryan