Todos los dispositivos iOS (itab, iphone, etc.) pueden mostrar videos mp4 y mov sin problemas, me extraña que, siendo mp4 el primero, no se pueda reproducir; tal vez los códecs no son los adecuados.
La única forma en que he podido reproducir videos en celulares (android) fue usando un servidor de streaming (WowzaMediaServer) y el video en formato 3gp; algunas tabletas android soportan perfectamente mp4.
Por cierto, algunos de los formatos que proporcionas no son soportados en navegadores, revisa esto:
http://www.w3schools.com/html/html5_video.asp
Teóricamente, bastaría con mp4, webm, ogv y 3gp para móviles... aunque no está de más un fallback con flv y reproductor en flash para navegadores antiguos.