I tried rolling my own millis() using an ISR. The ISR only increments a volatile global (absolute minimum).
It still loses time (about 3 seconds over a 1200-second interval) compared to my NTP-synced laptop clock. So it does seem that something (arctangent, SPI library.. or it could be Serial.print itself) is somehow causing both millis() and my custom ISR to lose ticks. Although I've reduced the frequency of the above to 1/second (hence only lose 3 seconds rather than 60). Time to look at an external RTC. Obviously I can't use the 1PPS to interrupt, I'd lose time too. I'll have to read the RTC in my main loop.