How should I respond to a terrible copyediting job?
That does sound terrible.  I haven't run into anything so bad myself, but I know people who have.  It seems to vary a lot by publisher.  My impression is that it happens occasionally when they try to save money on copyediting by outsourcing to a new, cheap copyediting company.  If the results are terrible, then the publisher will switch to the next-cheapest company, and this will continue until the publisher finds an acceptable level of quality.  Unfortunately, it leads to bad results for authors who get caught in the middle of this process.  Hopefully the publisher will learn from this incident and the problem won't continue.


  More importantly, is a strong response warranted?


Yes, certainly.  


  ask them to start over from scratch, and to furnish a list of all changes made, no matter how minor


I'd guess that getting them to start over from scratch will be difficult, but you should certainly insist on seeing a second set of proofs.

Asking for a list of all changes made could be useful, but it's not clear whether you can trust that they will compile a complete list (they may be sloppy about that too).  Many copyeditors mark up a paper copy before changing the file, so you may have some luck in getting a photocopy/scan of the marked up copy.

I'd also recommend letting the editorial board know, and perhaps the publisher too.  If you just resolve the issue directly with the copyeditors, it's possible that nobody else will find out what happened.