That doesn't explain how the report can run for over a year without issue, suddenly jump in time and stay at the longer time until SSRS is restarted. As soon as we restart the service, everything is back to normal for weeks.

If it were statistics, we shouldn't see the time drop again after service restart. No action was taken on the database itself.

If it were parameter sniffing, wouldn't it be spiking based on parameter? Or stay around the same time frame?