Are you able to write to a log file instead of the console? That may well be faster due to buffering and the lack of scrolling, displaying etc.
Do you actually have a console up while this is running? If so, try minimising it when you're not interested. My guess is it's the scrolling which is causing the problem.
EDIT: Okay, it seems some evidence is in order.
A few tests... I don't have XNA installed, but different ways of writing to consoles are still interesting. I wrote the numbers 0-99999 to various consoles:
- As a WinForms app, under the debugger, to the Visual Studio console: 135000ms, whether the console was visible or covered up.
- As a WinForms app, under the debugger, writing to a file: 160ms
- As a console app, not under the debugger, console minimised: 4149ms
- As a console app, not under the debugger, console not minimised: 14514ms
So as you can see, the Visual Studio console is painfully slow, a non-minimised "normal" console is next slowest, a minimised console is reasonably nippy, and writing to a file is very quick.
I stand by my advice to try writing to a file instead of the console, and otherwise if it's a standalone console, try to minimise it for most of the time.