Data lost writing on Arduino serial port. Overflow?
analogRead() will return 2- to 3 digit values, say 3. millis() will quickly grow to 4 and 5 character values, and with the tab and the newline, that's about 10 characters generated at each execution of the loop.

At 9600 baud, your serial port can write a bit less than 1000 char/sec or just under 100 10-character lines/sec. Your loop could easily run faster than 100 times/sec and if so the serial output buffer is undoubtedly overflowing. You need to delay 10ms or more in the loop for the serial port to catch up. 115K baud is 12 times as fast so you could reduce the delay (once you know how much you need) by that factor for the higher baud rate.