Yes, it seems the common factor is Firefox in combination with HTTPS everywhere. For some strange reason, Firefox tries to access search.cpan.org via HTTPS, even after completely removing "HTTPS Everywhere". I can access search.cpan.org from IE, so the problem is somewhere on my side. (I should have tested that before posting.)

Update:

It seems my FF profile is damaged, a fresh profile can access http://search.cpan.org/, but my normal profile forces a redirect to the non-working https://search.cpan.org/. Still searching ...

Created a new FF profile, without "HTTPS Everywhere". I still wonder what happened, but I won't investigate any further. I've already wasted too much time fixing that problem.

Alexander