[pja]

It used to be a complement IIRC: the US government set standards which were much tighter than those which were usually acceptable in the commercial world at the time & enforced them. If your work was "good enough for government work" then you were holding yourself to a higher standard than the norm for commercial manufacturing at the time.

[tcoppi]

How long ago was this a complement? I've never heard that phrase used in such a manner.

[pja]

WWII I believe: http://www.altus.af.mil/news/story.asp?id=123266336

If you do a google ngram search on the phrase, you'll see a blip during WWII and then nothing until 1970. I'm guessing the use from 1970 onwards probably carried the negative connotation we're all familiar with.