For example, the Congress’ subpoena of the Attorney General specifies “all correspondence” relating to several issues. How does anyone know if some documents are withheld?
Most correspondence (especially of the electronic variety) in business and government bureaucracy gets CCd and BCd to various people, so there’s usually more than one copy of a thing floating around–and often the people who hold those copies don’t share the same motivations or interests. When you get such a subpoena, your lawyer tells you to turn over everything, or risk additional charges like obstruction of justice which could result from withholding a document that someone else later presents. I think that fear is what they count on to get most of what they want, though if you really want to hide a document, maybe even that won’t stop someone from trying.
In many cases like this (political ones, rather than strictly legal cases) the side requesting the subpoena already has knowledge of what they should get.
For example, it’s likely the Republicans in Congress have ‘informants’ within the Attorney General’s office (leftover from the Bush times) who would likely let them know if something is withheld.
Likely too, there’s “due diligence”. In these days of online documents and indexed searches, if you simply do appropriate searches for the usual keywords that are relevant, and return everything that was flagged, you have probably met your obligation. You would probably be able to explain an accidental “miss” if it does not become flagged. OTOH, if it is a key, core document for the case, if it is not included in the response then be prepared to do some explaining. Plus, if they subpoena’d elsewhere and got a copies… Who do you know it was forwarded to?
When dealing with congress or the courts, it’s a very bad idea to play games. As Nixon remarked on his tapes (before he was caught this way too) the coverup rather than the original crime is often what you nail somebody on. (i.e. Alger Hiss).
You really don’t know. I work in local government, and we frequently receive requests for public records. I do try to pull all the documents I have, but I can’t be 100% certain I found everything there possibly is, especially if the documents are years old. I do take these requests seriously, and do everything I can to provide all the info, but I think it’s possible that there could be some unscrupulous people who might hold back certain things.
If it’s discovered that you failed to comply with the subpeona, you can be held in contempt of court, which can come with jail time and/or fines.
This was (kind of) mentioned in a records management course I took, and the fines for withholding documents (or destroying them unlawfully) are HEEE-YUGE. The courts realize that it is very easy for people to send documents through a shredder (or delete them) and just pretend they don’t have them, so the fines are very large to discourage that.
As an aside, every time you make a copy of a legal document, that needs to be kept as a record, too. So, think twice before you start making copies and cc’ing people. 
I’ll also add that someone is requesting this documents for a reason, so there’s going to be someone going through them, probably very carefully and suspiciously.
When that person sees a reference to ‘the memo of the 18th’, but can’t find the memo, they’re going to start asking more questions; likewise if there’s an e-mail with “re:” in the subject line, but no original e-mail, or if there are weekly progress reports for every week except May 23rd. Not that many documents are created in a vacuum. (and, as pointed out, at least some of the time the requester will know that certain documents exist, and know exactly what they want).