Okay, nach einigen Experimenten mit Lokutos bin ich auf die Idee gekommen, einfach einen Index auf Werbeart und kid zu setzen

Query-Time: 0.02s

Folgendes: Alle Indizes rauslöschen und dann folgenden Query:
Code:
ALTER TABLE `vms_fb_blacklist` ADD PRIMARY KEY ( `kid` , `werbeart` , `sponsor` )