I usually run the output into less so that I can kill it via less instead using the q key.
$ cmd | less
Example
$ cat /dev/urandom | less
After hitting q+Enter it'll quit and return back to your normal terminal, leaving it nice and clean.
Why does that happen?
The problem you're encountering is that there are buffers (for STDOUT) that are being queued up with the output of your display. These buffers get filled so quickly that you're unable to interrupt it fast enough to stop it.
                                    
 To disable/limit this effect you can disable the STDOUT buffering which should make things a bit more responsive using stdbuf, but you'll likely have to play with these settings to get things the way you want. To unbuffer STDOUT you can use this command:
$ stdbuf -o0 <cmd>
 The man page for stdbuf details the options at your disposal:
    If MODE is 'L' the corresponding stream will be line buffered.  This 
    option is invalid with standard input.
    If MODE is '0' the corresponding stream will be unbuffered.
    Otherwise MODE is a number which may be followed by one of the 
    following: KB 1000, K 1024, MB 1000*1000, M 1024*1024, and so
    on for G, T, P, E, Z, Y.  In this case the corresponding stream will be 
    fully buffered with the  buffer  size  set  to  MODE
    bytes.
For a nice background on how buffering works I highly suggest taking a look at this Pixel Beat articled titled: buffering in standard streams. It even includes nice pictures.
