Ich hatte früher ein paar Seiten bei sponsorads.de - haben immer zügig ausgezahlt. Ist allerdings schon ca. ein Jahr her. Gezahlt wird hauptsächlich für Auslieferungen und Klicks.

bei dem er seine Auszahlung von über 500 Euro (!!) beantragt hatte und dann gesperrt wurde.

Mit welcher Begründung? Sofern widerrechtlich gesperrt wurde, gibt es hier ja durchaus Möglichkeiten, die Ansprüche geltend zu machen. Sofern man sich an die Regeln hält, wird aber wohl auch kein seriöser Anbieter die Zahlung absichtlich verweigern bzw. den Account sperren..

Euros4Click.de hab ich auch mal genutzt, Geld kam da auch immer - ist allerdings auch schon etwas länger her.
Ansonsten kenne ich noch Binlayer.com - habe ich allerdings nie genutzt und es gab da letztens noch Insolzenzgerüchte (da irgendwelche Sponsoren nicht gezahlt haben) . Müsstest du mal suchen, ob die das geregelt bekommen haben.

Prinzipiell kann man aber viele Anbieter einfach ausprobieren. Meistens liegt die Auszahlungsgrenze ja irgendwo bei max. 20€ - da würde ich mir dann nicht hunderte von Euros ansparen, sondern die Auszahlung sofort anfordern. Wird nicht gezahlt, wechselt man den Anbieter, fertig.

Welcher Anbieter der Richtige ist, hängt meistens auch von deiner Seite ab. Für halblegale Seiten kann ich eAds.to empfehlen, bei "normalen" Seiten sollte man schon schauen, wo die Firma sitzt.

Ich arbeite übrigens auch bei einer Werbefirma mit Sitz in Berlin. Wir heißen Plista und haben sehr viele Publisher aus dem Verlagswesen, darunter Spiegel Online, Welt, Sport1.de, ...
Soweit ich weiß zahlen wir ab 70 EUR aus. Je nachdem was für Ziele der Advertiser verfolgt, wird nach Impressions, Klicks oder Conversions abgerechnet. Das sollte aber nicht für dich relevant sein, denn letztendlich muss Werbung für beide Parteien fair sein

Ich werde in dem Posting keinen Vergleich der Anbieter anstreben, sondern dir ein paar Fragen stellen, damit dir klarer wird, was du eigentlich suchst

* Willst du dir die Werbepartner selbst aussuchen oder lässt du den Werbepartner das machen?
Mit Affiliate Netzwerken und Partnerprogrammen (z.B. Amazon) kannst du konkrete Produkte empfehlen und damit Geld verdienen. Das funktioniert sehr gut, wenn du auf deiner Seite zu irgendeinem Produkt schreibst.
Alternativ bindest du ein generisches Widget ein und lässt deinen Werbepartner entscheiden, welche Werbung auf deiner Seite erscheint. In dem Fall hängt die Qualität der Werbung natürlich davon ab, welche Advertiser der Partner gewonnen hat, wie gut die Werbeoptimierung ist und wie groß das Publishernetzwerk ist (um so mehr Informationen der Werbepartner über den Benutzer hat, umso besser die Werbeempfehlung).

* In welcher Optik willst du die Werbung denn zeigen?
Meistens halten sich die Werbefirmen an die IAB Standard Formate (300x300, 468x60, etc).

Hast du diese Fläche erstmal auf deiner Seite reserviert, soll es den Text Only sein? Oder Text-Bild Kombination? Oder reine Bild Werbung?
Mitunter fühlen sich vielleicht einige deiner Besucher durch zu auffällige Werbung gestört.

Es gibt diverse Formate, ich ich persönlich einfach nur als störend empfinde. Dazu gehört z.B. das pagepeel. Diese zielen eher auf Zufallsklicks.

* Willst du spezielle Formate monetarisieren?
Hast du eine Bildergallerie, kannst in den Bildern Werbung anzeigen.
Hast du eine Videoseite, kannst du in den Videos oder vor dem Abspielen des Clips Werbung anzeigen.
Mit Intext werden Wörter wie "Auto" unstrichen und beim Hovern mit der Maus wird passende Werbung angezeigt.

Ich bin aber auch am überlegen, ob ich mich bei mehreren Werbeanbietern anmelden soll, und dann per Zufallsgenerator entscheiden lasse, welche dann angezeigt wird.

Vorher bitte GANZ GENAU die Regeln der entsprechenden Anbieter lesen, bei den meisten fällt das unter "Wahrung der Exklusivität" und ist verboten.