Colored terminal output does not reset

While writing a larger program I stumbled upon a small problem with colored text output. Here's a much simpler program that reproduces this issue.

#include <stdio.h>

#define COL_RESET "\033[0m"
#define COL_BG_RED  "\x1B[41m"

char *str = "the quick brown fox jumped over the lazy dog";

int main(int argc, char *argv[])
{
    int i = 10;
    while (i) {
        puts(COL_BG_RED);
        puts(str);
        puts(COL_RESET);
        puts(str);
        i--;
    }
    return 0;
}

Now this is what I get when I run the program:

First time - expected result

Second time

As you can tell, the program decides to randomly print lines even after resetting the colors in red. When started in a fresh terminal it always prints the expected result. Unless I run clear, there is no guarantee the output won't be mangled like in the second picture.

In the pictures I'm using xterm, although other terminals do the same thing.

What can I do to prevent this?