Drauf gekommen bin ich darauf, indem ich noch mal meinen Kopf angestrengt habe. Da ist mir eingefallen, dass ich bei Wikipedia schon einmal so ein ähnliches Problem hatte, als ich die API genutzt habe.
Damals habe ich sehr lange gesucht und bin dann in einer Mailing-Liste für Wikipedia-API-Entwickler fündig geworden. Ich denke, dass ich auch ein sehr spezielles Problem, wenn man Requests an Wikipedia stellt. Keine Ahnung, ob es bei anderen Seite auch vorkommt.
Die Lösung war ja dann letztlich einfach. Einfach vor dem Request diese Zeile einfügen:
ini_set("user_agent", "Twick.it");