I have found one option that affects it. Switching on sprite edge smoothing gets rid of the black boxes.
Here's what it looks like:

However, it isn't all sprites and it isn't all of the time.

Sometimes just moving is enough to "toggle" the effect.


Although these pics are all of my Incas and that they all have translations, I have seen it with other untranslated sprites - eg a Hexen Demon. However, it seems very easy to repeat it with my mod for some reason (Burghead seems to show it reliably).
Going back to r663 (the most recent build that I had handy) fixes the issue.
[edit] For the sake of completeness, I had the presence of mind to screenshot this. Interestingly, I'd been playing for about an hour with no glitches prior to getting this.

Well lit areas and possibly areas with sky do seem to show the effect more often, but I have seen it in duller areas with normal ceilings too.
[/edit]