Moin,
gibt es eine Möglichkeit, schnell zu prüfen, ob eine bestimmte
Wunschmailadresse bei einem Webmail-Anbieter noch frei ist?
Nein, so eine Möglichkeit gibt es generell nicht, es sei denn, der Mailanbieter bietet sie an. So etwas wie die DENIC für Mailadressen gibt es nicht. Wäre ja auch eine Einladung zum Spammen, man braucht nur abzufragen, welche Mailadressen existieren, bevor mal SpamMails verschickt.
Ich möchte nicht hundert Websites aufsuchen
Du kennst so viele Anbieter? 
Da wird dann aber doch wenigstens einer dabei sein…
Welcher Mailprovider es ist, ist eigentlich egal, er sollte
nur kostenlos sein.
Geiz ist geil?
Ansonsten kann ich nur empfehlen, sich bei einem Webspace-Provider einen „Visitenkarten-Webspace“ zu mieten, den gibts bei vielen Anbietern und kostet oft nichtmal einen Euro im Monat. Da bekommst Du eine eigene Domain dazu und meist zumindest eine Mailadresse.
Da kannst Du Dir dann Deinen Wunschnamen selber aussuchen.
Viele Grüße,
-Efchen