Acho que é raro mas já vi mp4 com softsub.
Deis, você consegue desabilitar as legendas ou elas estão aparentemente "grudadas" na imagem? Se elas forem grudadas na imagem é chamado de hardsub, se as legendas estiverem separadas da camada do vídeo então é softsub.
Se for hardsub só sendo bastante engenhoso: passar o vídeo por um OCR ou algo assim.