Cannot play .mp4 videos with the default video player
You habe 2 choices:


Download another media player such as VLC, MX Player, etc, then test the videos with them to know for certain if the problem is isolated to only the native video player or not. These apps are better than the phone native video player, come loaded with more codecs and can play more formats. However, you said you didn't want this solution.
Convert the videos to the appropriate codecs, resolutions, bit rate and other parameters recognized by the phone's video player. You will have to 'duplicate' the playing video parameters to the non-playing videos by checking the differences between them. Then, you can convert them on your PC before transferring them to the phone.