Lange Rede kurzer Sinn:
Welches Release hast du?
Sind die PTF's ggf. nicht aktuell?
Prüf doch mal ob es zu aktualisierende PTF's gibt.
Wann ist der letzte RCLSTG mal gelaufen?

Wenn ich auf der mir zur Verfügung stehenden Maschine einen SQL auf eine Tabelle mit 41 Mio Sätzen loslasse der einen Tablescan erfordert, läuft dieser ca. 20 Sekunden.

Wie lange läuft bei dir dann also ein
Select * from TableA where FeldA <> 'XXXX'
und
Select * from TableB where FeldA <> 'XXXX'