Skoro zmiana filtrów pomaga, to może dlatego, że sql przetwarza nowe zapytanie, buduje nowy plan zapytania i lepiej może sobie z nim poradzić.
Można więc wspomóc sql server i kazać mu przegenerować własne statystyki na potrzeby planów zapytań, wykonując za pomocą management studio:
USE Nexo_<nazwa_podmiotu>;
GO
EXEC sp_updatestats;