Significant Arduino execution delay every time I open Serial Monitor

Hello,
Recently, I've run into some trouble involving serial communication with the Arduino. Every time I open Serial Monitor, the execution of code on the Arduino seems to pause for a significant time (10 seconds or more). When execution resumes, the millis counter has been reset, but everything else proceeds as normal, even when I close the monitor. Only when I open the monitor does the problem occur. I have not always had this problem, and until recently the Arduino worked as normal. I have tried reinstalling the drivers, using different computers and cables, changing the COM port in device manager, and removing and re-downloading all Arduino software on my computer, but all to no avail.

Specs:
Windows 7 Ultimate
Arduino Mega 2560 on COM3
USB connection to computer
Nothing besides the USB cable attached to the Arduino

The problem happens regardless of whether I'm running a sketch that uses serial communication. For example, when I run the example Blink code, everything at first works fine, and the LED begins to blink. As soon as I open Serial Monitor, the LED freezes in its current state. After about 10 seconds of Serial Monitor being open, the LED once again begins to blink as usual.

When I run this simple serial code, I get the same results. The TX LED begins blinking after I deploy the code. As soon as I open the Serial Monitor, however, the LED stops blinking. After the delay, it begins to properly display the times, starting with 0. Every time I close and re-open the monitor, the millis counter resets itself to 0.

void setup() {
  Serial.begin(9600);
}

void loop() {
  Serial.print("Millis: ");
  Serial.println(millis());
  delay(1000);
}

Any ideas what could be causing this? At first, I suspected a software issue, but I'm worried that the Arduino may be damaged somehow. Any help, ideas as to what could be causing the problem, or suggestions are appreciated.

EDIT: Never mind, my bad. Apparently most Arduino boards will auto-reset when Serial Monitor is opened, resulting in a delay. I'm not sure how I didn't notice the delay earlier. Sorry for the unnecessary post.

...the execution of code on the Arduino seems to pause for a significant time (10 seconds or more).

A different bootloader will significantly reduce that time. I believe Optiboot takes only about 1 second to start the sketch.

If you don't want the board to reset when opening the monitor you can try this:
http://forum.arduino.cc/index.php/topic,118440.0.html

BTW reset is still available, but as a button in the monitor: