El problema no es que tengan la versión 5.0 solamente. Ni que trabajen con PHP y MySQL.
Por eso te dije que deben darse AMBAS condiciones (Versión 5.0 o superior Y tablas InnoDB).
El tema es que las InnoDB son funcionales en cualquier contexto, pero en la Web las MyISAM son más eficientes (el por qué, requiere una larga explicación).
El problema en este momento es que MyISAM no acepta transacciones (ni tampoco dependencias relacionales), y por eso simplemente ese servidor no sirve.
Tendrás que andar para encontrar uno que te brinde el soporte de transacciones, así que investiga un poco más, por mi marte con una simple consulta en Google (
web hosting MySQL InnoDB) encontré:
-
www.olnevhost.net/
-
hosting.solingest.com/
-
blog.eukhost.com/
Estos y otros dicen ofrecer MySQL con tablas InnoDB.
tu dirás si es cierto.