And I can say 'nothing has changed' with all the credibility that a programmer can summon when s/he says that :)
I since found a query someone else was running (emphasis on the 'was' part), and it's now picked up the pace to a blinding 4 rows per second.
Darn.
/me wanders off to find the 'please reboot this box' paperwork :(
If only there was a 'convert to Oracle so it might actually work' form :)