El problema se llama "Alcoholes Decembrinos y Mykire"
¿Degragmentas tus índices?
¿El rendimiento general del sistema cayó o solo es algo focalizado en una o dos tablas (o una o dos consultas)?
¿Revisaste el Performance Monitor del servidor, dentro de Windows, no de SQL Server? Para descartar problemas de cuellos de botella en RAM y procesador.
¿Reiniciaste el servidor? Da risa a estas alturas, pero los míos procuro hacerlo 1 vez por semana por aquello de los parches de Windows y la propia sanidad mental de Windows.