What's the best way to display thousands of polygons in Openlayers?

I don't like the BBOX strategy as I think it might be slow due to the amount of requests that may be generated.

I would use a combination of both things you mentioned.

display polygons with WMS and use getfeatureinfo... then use WFS, to load outline the feature when clicked on and/or get more information from the database.

protectedplanet.net doesn't use openlayers just google maps. They are probably storing all the information in a KML/KMZ.

The main approach here is to separate rasterization with interaction. One approach (that I'm partially responsible for) is UTFGrid, which has been used by NPR, etc and is integrated into TileMill and Mapnik. It's also used by CartoDB and Google Maps uses a similar approach for Fusion Tables.

Protected planet uses raster tiles as well (for instance, this one: http://184.73.201.235/blue/8/78/93 ) and has a live server behind it for point-based queries (for instance, this one).

Re: CaptDragon: there's no WFS or KML involved.

WMS and WFS will not give you anywhere near good enough performance for a public site. The BBOX strategy will not work if you let users zoom.