A lo mejor estoy diciendo una tontería, pero por que en vez de comprobar los enlaces cada vez que se solicita la pagina, no creas un proceso que se ejecute a su aire y que este continuamente comprobando los enlaces de la base de datos, no hace falta que que este proceso tenga mucha prioridad para así no interferir con el resto de procesos del servidor. Cuando este encuentre un enlace no valido, lo marcaría en l base de datos. Así cuando se solicitara una pagina se podría saber si el enlace sigue siendo valido.
No es una solución en tiempo real, a lo mejor un enlace puede dejar de ser valido y no enterarte hasta horas después cuando le toque ser comprobado, pero no creo que el beneficio de comprobar los enlaces en tiempo real compense la carga de trabajo para el servidor que eso supone.
En cuanto a lo de comprobar un enlace sin usar http, lo veo difícil. Con un "ping de esos", como tu los llamas, solo puedes comprobar que el nombre del dominio es correcto y que el servidor esta funcionando, pero no si un determinado documento ha sido borrado. Además una simple petición HEAD para saber si el documento todavía existe no debería de consumir mucho tiempo.
Bueno, ahí te dejo mis divagaciones, pues en realidad no te aporte nada tangible
