Nobody can tell you anything without exact details. You have written a lot, but not provided any shred of useful info - no render settings, no output settings, no info on how you actually verify your audio, no details on your audio settings on the systems and AE's audio prefs, no cache settings. The list could go on and on. All you ever do is throw around generic mentions of MP4 files and AVI when the latter of which is merely a container format that can have a million different CoDecs and settings inside. Really, nobody can make anything of your write-up, least of all help you track down the problem.
I smell a rat -- a Compressed Audio Rat, to be specific.
AE has NEVER been good with compressed audio. If you are using mp3 or ac3 -- actually, anything other than wav or aiff -- you're taking chances and you should convert them.
@Dave LaRonde Thanks a ton, your suggestion fixed my issue.
@Mylenium Thank you for the help.