MySQL: Indices richtig setzen

[Hannes]

Schönen Tag liebes Forum,

ich habe hier eine Abfrage:

SELECT
 pk_id
FROM
 myTable
WHERE
 veroeffentlichungsdatum >= '2006-01-01'
AND
 schlusstermin < NOW()
AND
        schlusstermin <> '1900-01-01'
AND
 pk_id NOT IN ( 94923,94924,5345345,34534,534545,546,756,7567 )

die über eine sehr große Tabelle mit ca. 500.000 Datensätzen geht.
pk_id = Primary Key
Jetzt habe ich schon ein paar Varianten mit Indices versucht, damit die Abfrage schneller geht, denn in:
pk_id NOT IN ( 94923,94924,5345345,34534,534545,546,756,7567 )
stehen, dann bis zu 300.000 Ids, die nicht mehr selektiert werden sollen und dies wird mir leider beim Index:
pk_id, veroeffetnlichungsdatum, schlusstermin
nie genommen.

Wie muss ich also die Abfrage umbauen, oder einen Index verwenden, damit diese Abfrage schnell wird?

Danke jetzt schon für die Hilfe.

Hannes