I tested this against my existing py3k nttp client code.

Why is it a good thing to make file a keyword only parameter? But given that it is, line 720 needs to use it as such, which omission means your missing at least one test :)

On line 193 you index fmt, and *then* you check the length.  When the number of tokens is too long, an IndexError is raised.  (Note that the offending overview line comes from the gmane group comp.lang.python.mime.devel, and the offense is an extra '' field on one of the records.  No idea why it got added to that one record.  Looks like it is message 701, artid <4111BBA9.3040302@harvee.org>)

Could the 'date' field in the xover headers also be a DateTime rather than a string?  And :bytes and :lines be ints?  Or is that being to DWIMish?  If the date field isn't returned as a datetime, though, should there be a helper method for converting it, or should we just assume that email.utils mktime_tz and parsedate_tz?

Am I correct that the purpose of _NNTPBase is to make testing easier?

There seem to be only three lines of code in common between the file and the non-file case in _getlongresp.  I think it would be clearer to make them two different routines, or at least move the three common lines to the top and then do an if test on file is None (that is, put the simpler, non-file case first).

My little nttp client script doesn't really test very much of the nttplib interface, nor is it very complex.  The change to xover considerably simplified that part of my script, so I very much like that change.  I was also able to drop my implementation of decode_header.  So overall this patch is significant improvement, IMO.

I haven't given the code as thorough a review as might be optimal, but I certainly think you are headed in the right direction.