A site restart should not be neccessary!
Are you using a CDN, or some kind of external cache? Do you have a load-balanced server setup?
Site restart is not required but as Tom suggested this is definitely a caching issue or load balancer server issue.
If you are not DXP then try clearing caching from the Paasportal troubleshoot tab.
When a pages URL is changed, it seems the website does not recognize the change until restarting. Is there any way to have this get updated on change, or to perhaps schedule a job that can update page URLs? Having to restart our whole site causes downtime and we want to avoid disrupting our users experience. Are there any alternavives? I've done some searching and couldnt find anything on the subject.
Thanks in advance!