Though I still use PHP4, I agree that it's on its way out. PHP5 has already been released for quite some time now and as such as been improved through bug/security fixes. If you are looking for a webhost and find that some of your candidates don't support PHP5... don't even consider them as possible candidates.
My (shared) webhost uses server clusters - all are mixed PHP4/PHP5 (AFAIK). The cluster they assigned me when I initially signed up had PHP4 as the primary parser - .php files were handled by a PHP4 DLL, .php5 extension was parsed by a PHP5 CGI binary. After simple help ticket request I was immediately moved to a cluster where PHP5 handled .php requests.