For several versions of IDEA (4.0.x, 4.5.x, 5.0.x, and now 5.1.x) the combination of cvs and ssh doesn't work with certain cvs servers. The most recent is my Sourceforge project for my IdeaVIM plugin. All other cvs clients have no problem accessing that cvs repository but IDEA can't access it at all. All I ever get is the "Valid requests expected!" error.
As some others have determined in the IDEA forums, it appears that this problem only happens against certain versions of cvs and possibly when the server is on a specific OS.
Sourceforge recently redid all their cvs servers so this is a new problem with Sourceforge. But at least this gives you a good concrete example of when your cvs code won't work.
Basically no one with a Sourceforge project can use IDEA anymore with CVS. This is critical for me.
This assumes a CVSROOT of the form :ext:user@host:/path and CVS_RSH=ssh
Rick