Why do I need to wait a few moments before sending serial data on my AVR?

I have an AVR (ATMega644) connected to a Raspberry PI via serial connection. The AVR is powered with 5V and the AVR=>RPI Tx line is using a 1k8/3k3 voltage divider to get a 3v3 level.

If the 10ms wait (XXX in the code) is not present (according to the data sheet I do not have to wait at all) I receive this nonsense (python repr() of the received data):

 '\x00\xaa\x8a\x8a\xea\n'
 '\xe9\xf5%\xc5E\xd5\xa4\xfcBYE WORLD\r\n'

When the 10ms delay is there I receive this:

'\x00HELLO WORLD\r\n'

'BYE WORLD\r\n'

This is pretty much fine. I'd like to know why there's a \0 before the very first actual data byte ('H') though. I never send one for sure!

However, my main question is why the delay between initializing and sending data is necessary.

Notes: My F_CPU value is correct and so are the fuses. I also tried using a lower baudrate (4800) and a different chip.

This is the code I'm using:

#include 
#include 
#include 



inline void uart_putc(char c)
{
    loop_until_bit_is_set(UCSR0A, UDRE0);
    UDR0 = c;
}


inline void uart_puts(const char *s)
{

    while (*s) {
        uart_putc(*s++);
    }
}


int main()
{
    // we don't need/use any interrupts
    cli();


    // -DF_CPU=18432000L -DBAUD=19200 used when compiling
    UBRR0H = UBRRH_VALUE;
    UBRR0L = UBRRL_VALUE;
    // 8 data bits
    UCSR0C |= (1 << UCSZ00) | (1 << UCSZ01);
    // enable transmitter
    UCSR0B |= (1 << TXEN0);

    _delay_ms(10);  // XXX

    uart_puts("HELLO WORLD\r\n");
    _delay_ms(250);
    uart_puts("BYE WORLD\r\n");

    // do nothing
    while (1)
        ;

    return 0;
}