>> I was hoping that someone would be able to give me a better solution because the analyzer shows table scans and even with indexs it doesn't perform any better.
This doesn't surprise me. It's difficult for the optimizer to optimize NOTs. You could try converting to an outer join and looking for NULLs:
SELECT id FROM b WHERE b.id NOT IN (SELECT id FROM a)
becomes
SELECT id
FROM b LEFT OUTER JOIN a
ON b.id = a.id
WHERE a.id IS NULL
-Mike