I'm pretty sure the hardware UART does not rely on interrupts and it would be fine to use it in an interrupt handler.
Even if you were using software serial, you could simply set a flag in your interrupt handler and then from your main code, frequently check if the flag is set and if so, send the packet and clear the flag. Thought that would basically be what it's already done (mills is pretty much a flag being set by an interrupt handler).
I think Oracle missed out on his morning coffee before posting the above
Mikal is correct, the Arduino hardware serial UART does use interrupts, so one should avoid calling hardware serial functions inside an interrupt handler if you don't want to risk dropping characters. (the handler is in wiring_serial.c)
Millis() returns a calculation based on a counter incremented in the timer interrupt, so unlike with a flag, you actually need to compare the value returned from millis() with a previous value to determine how much time has passed.
It's not clear how accurate the timing needs to be between messages but my suggestion is to poll the standard millis function to see if the correct amount of time has passed for sending the next message.