It seems that this happens, but how many and how often, I guess that depends on the hosting company their methods etc etc
www.HostMySite.com lets you choose PHP4 or 5 with just the click of a button. They're my preferred provider for shared hosting.
Most hosting services offer the option to switch from php4 and php5 at your convenience either from your control panel or adding a few lines to your .htaccess. However most services advice you stick to php4 because php5 runs like cgi increasing your resources and bandwith consumption, at least is what they say.
Only if they don't know how to set it up as a shared module, or they're running Windows. Both reasons to avoid the host in the first place.