By using Special:Permalink, the link is blue even if the page no longer exists. If clicked, the user gets a cryptic error like:
The revision #110161448 of the page named "Main Page" does not exist.
This is usually caused by following an outdated history link to a page that has been deleted. Details can be found in the deletion log.
If the page has been deleted, we should just link to it so a redlink shows up.