Using tinyGPS++ with millis errors
You're only reading from the serial port every GPSSearchPeriod milliseconds. That gives plenty of time for the small serial read buffer to overflow and lose the data.

Instead you should be reading all the time regardless of your desire to only do things periodically. Sure, report the data periodically, but you must read all the time as well.