Does this apply to the hardware serial port only or also to software serial ports (e.g. NewSoftSerial)?
While sending a byte, does the interrupt get lost or does the ISR automatically get called once the byte has been sent?
No. During sending of a character, interrupts are disabled, so that all bits are send together. The are enabled again until the next character needs to be sent. Your interrupt can only fire when interrupts are enabled. It will cause serial data sending to be on hold while your interrupt does it's thing, so you need to make it quick.