A meno che tu non usi delle funzioni non presenti nelle versioni 4.x di php, tutto dovrebbe funzionarti.
Io non sono molto informato sui servizi di hosting, il mio è [CUT BY GM]. ho chiesto il supporto al php5 e, tempo che si aggiornassero i dns, tutto è partito.
cmq, fai una ricerca con google, vedrai che ce ne sono molti di hosting che offrono supporto al php5
