I really like this one. I heard it a few years ago, and remembered my solution because it was neat. However, I had forgotten the question (and have been intermittently searching the internet for it) until now. Thanks! (It is a bad thing to have an answer without a question floating around in your head!)

Thompson's Group $F$ be may a good bet. To begin with, it does not contain any free subgroups (see the proof that it is not elementary amenable). However, the questions of ameanbility and exactness are (to the best of my knowledge) both still open. As a note on exactness, it does have Hilbert Space Compression equal to 1/2 (if it was >1/2 then it would be exact) by a paper of Arzhantseva, Guba and Sapir, so it is epsilon-close...

I agree wholeheartedly. I feel that Pure Maths is more relevant to, and has more in common with, CS than Stats, and yet my department is in the middle of combining with the Stats school.

I have come across both of these links, and in some ways the first was my reason for asking this question. The conversation dies down in the middle of January (5 months ago, and this all kicked off about a year ago) having established that Akhmedov's paper needed closer scrutiny.