Lol, who is your hosting company?
They should try to get to 4.4.0 for the recent fix, but 4.3.11 will be fine and MySQL 4.0.25 as well.
I'm run a hosting company, I know others who do as well, I've never run php as a CGI process due to its overhead. I know many hosting companies do not run php as a cgi, mostly the better ones
If your intrested in looking for a new host let me know