So, your problem, despite the thread title, has nothing to do with ethernet. Right?
Still, the behavior is not normal. You'll have to remove the randomness. That is, you'll need to determine what the pattern is. What other serial devices do you have? Are you running any kind of bluetooth software? Something that tries to connect to all the serial ports to see if there are bluetooth devices connected?
I have experienced this problem with the webserver, webclient, telnet client in the examples with the ethernet library, also with SDwebbrowse.ino from the Adafruit site. I have a Windows 7 PC, Arduino 1.0.1 IDE, Mega, Ethernet shield and a LCD. It happens both with and without the LCD attached and with and without the LCD required libraries. When the Ethernet shield is not attached it does not happen. The program I'm working now is an extension of the SDwebbrowse program. I can add something as insignificant as lcd.print statement, go to reload and it happens. I save the program, reboot and reload the program, it will recompile and download correctly. The attached libraries are: