So.. they said please, didn't threaten you, and pointed out a few potential problems with the method you are using (like missing return addresses). That seems.. helpful?
They were certainly polite. :) I did a quick check for people submitting things like "FUCK YOU" and "YOUR MOM" in every field and deleted those before sending. A couple I let through had things like missing city but valid ZIP code, which I assume would actually be enough to get the letter to them. 95% of what was sent had a full address.
Did you ever read their instructions for filing a FOIA request? "If you do not include a name and complete postal address, NSA will be unable to respond."[1]
While you are here I dont understand what you mean by:
"It seems that the NSA does not quite get that this is a protest, in addition to a request for information."
How did you expect them to act? And/or what behavior would constitute recognition that this is a "protest"? NSA is required by law to respond to FOIA requests. The civil servant that emailed you was doing what her employer told her to do so that she could continue to bring a paycheck home. Are all the "protest" FOIA requests supposed to get tossed in a burn bag at the end of the day?
[1] http://www.nsa.gov/public_info/foia/submit_foia_request/foia...