Ja in der Tat habe ich eine Lösung für das Problem gefunden...kommt mal alle wieder runter. Heute ist Freitag, seit Mittwoch scheint der Fragesteller zu schlafen.
Gute Nacht!
In erster Linie halten wir fest, dass wir nicht um den Umbau der Tabelle herum kommen (Stichwort Normalisierung, vielen Dank für den Tipp akretschmer)
Als schnelle Abhilfe habe ich die StorageEngine der Tabelle von InnoDB auf Aria geändert und konnte die Abfrage so von >1 Min. auf etwa 15Sek. runter drücken...