[UPDATE: The comments have been very interesting; I have a post on a plausible, though limited, answer here.]
I confess I'm pretty puzzled by Speaker Hastert's theory here. I understand that the power to arrest, search, and prosecute Congressmen could be abused by the Executive. But I take it that Speaker Hastert isn't arguing that Congressmen can't be prosecuted, or even can't be prosecuted for bribery. (Actually, Justices Douglas, White, and Brennan seemed to take the latter view in United States v. Brewster (1972), at least as to the selling of legislative acts; but they lost, and I hadn't heard of anyone trying to revive this position.)
Is it that Jefferson could be prosecuted, but his office couldn't be searched? If so, what exactly is the constitutional basis for the distinction? For now, my tentative view is the same as Orin's — there's no constitutional problem here — but perhaps I'm missing something.
If you have some thoughts about the constitutional issue, either for or against the argument that the search was impermissible, please post them. Please stay away from general speculation about the politics or ulterior motives of the matter; such speculation may be quite interesting, but I just want to keep this particular discussion thread focused on the constitutional question.