Seems questionable to me also, but my understanding was that it's legal (and common) for employers to routinely read communications that take place on company-owned equipment. Do they have to stop reading it if they realize that the employee is communicating with an attorney? Or is it up to the employee to avoid using employer equipment for such purposes?

edit: Some searching digs up that the ABA model code of conduct suggests to attorneys that, as part of their duty of confidentiality, they should warn clients not to email them from their employer's email address. So it seems that the ABA is at least wary of whether such email would be confidential.

This is more complicated because their employer is an agency of the United States federal government.

True, that does complicate it a bit. I'm not an expert in this area by any stretch, but from what I've read, employees' rights are still pretty strongly curtailed. The courts have generally held that the government acting in its role as employer, rather than its police-power role, has roughly the same authority as a private employer would have with respect to its employees. The test for which role it's acting in at a given time is basically whether the search could reasonably be considered work-related. http://en.wikipedia.org/wiki/Ontario_v._Quon was a recent case.