@Brian: You 'recycled' my robots.txt

What Google doesn't like might be the "double content" caused by the different views and order possibilities (different URLs with the same content).

Yes, that's exactly the problem. Details are given in the english forum, and more deeply in the german one.

In the current version I reduced as much as possible the query strings for page numbers, categories and the order of threads in the URLs ...

That's nice (long URIs are often 'broken' if copied from a browser's address-line and sent via e-mail), but concerning search engines a 'maximum depth' of 4 parameters (and the like) are simply a myth.
Since only one view will 'exist' in the new version, I would not expect double content to be an issue any more.

... but maybe a robots="noindex" in all pages except for the index page and the opened messages might also be beneficial.

Oops, please as an option only (if at all)!
Just imagine how the crawler would work:
- The index page contains only the headings of threads and links (is rated as a 'link collection' which crawlers don't like, because they want to find keywords for their database)
- In order to crawl the individual posts they have to follow these links, which may take a while (Google is a daily guest in my forum for about 6 hours)

The variant with robots.txt + modified scripts (rel="nofollow" at corresponding links) is working perfectly.
Since robots.txt and rel="nofollow" are non-binding conventions. it's always a good idea to use both of them.

I'm using my forum in mix-view and changed the default order of posts to last-answer. By this not only new posts, but also replies to older ones are displayed in the entry page (which is crawled first).
forum.php, line 41

  if (empty($order)) $order="last_answer";

instead of

  if (empty($order)) $order="time";

It's also a good idea to change the subject line according to the content of the post. Everybody should suggest such a procedure is his/her forum's FAQs. If you want to get better search results, admins and mods should edit subject lines as well - although this may not be an option for pretty large installations.