Its a little of both. If you had rebooted again after getting the new modem it would have picked up an NTP update and thus fixed itself. What happened is with your modem out, and you rebooting the R4S, it lost its time (because it doesnt have a RTC). Without a proper time sync, you cannot do encrypted dns lookups as it requires proper time/date to be set. Once you updated the time, it all fell back in place and carried on. This is why we either use unencrpyted DNS for NTP updates or put a NTP bypass in place.
Regarding the battery for the R4S, I investigated that and if you look on the R4S thread and on the wiki, i have posted pictures showing a rtc battery vs the case of the r4s. It would not be an easy fit. Potentially you could drill a hole in the external case and just tape the battery to the side or maybe use a smaller battery.