The latest and greatest php version is always the recommended version. Seriously. All core devs use it when developing trunk. Only a few bother to test older php versions, as can be seen by the occasional ticket opened related to php4 or php5.x incompatibility.
The same cannot be said by plugin authors, however… As you pointed out…