Problem is it appears I am sometimes loosing a byte or two in the data stream along the way.
Quite possibly, you are. You seem to be operating under the assumption that the serial buffer size is unlimited (it is not) and that serial data is guaranteed to be delivered, uncorrupted (it is not).
This causes a big problem for me as there is no way to determine along the way which segments are complete and which are missing a byte unless the entire message is recieved and the position in the array of the end byte pair can be found.
Then, the sender needs a re-write.
Is it possible the device is sending bytes faster than the ATMEGA2560 can read them from the buffer?
Yes, and no, It is not possible to fill the buffer faster than it CAN BE emptied. On the other hand, it is quite possible to fill the buffer faster than it IS emptied.
Writing serial data while reading is slow. Actually, writing anytime is slow, but doing so while reading interferes with your ability to read as fast as possible.
Serial.println("collected raw gps data");
The intent of that long collection of characters could be conveyed in far fewer characters.