First off, I've tried re-encoding them to 44 & 22 kHz, all have the same issue.
So, I've got a page with an audio link. Some IE users report that when they click the link Windows Media Player says that it has "reached end of file" and doesn't play it. I found that if you right click and save the file, then play it on those machines it works just fine - when loaded from the local disk - so the MP3 file itself isn't corrupt. I have not been able to replicate the error in Firefox (even using WMP).
In trying to resolve the issue, rather than link to the file, I thought I would embed it, using this player. But the player also refuses the play some of the MP3's. I have NO idea what's going on, my boss is pressuring me because the CEO is pressuring him & I'm at my wits end. Any solution gratefully received!
Sample links:
Non-working MP3:
http://wap.test.linguaphone-intranet.co.uk/RW5nbGlzaA%3D%3D/5pmu6YCa6K%2Bd/content2.php?rubric_id=12...
Working MP3:
http://wap.test.linguaphone-intranet.co.uk/RnJhbsOnYWlz/VMO8cmvDp2U%3D/content2.php?rubric_id=1189
P.S. It's also not the phrase length (file-size) as the working ones also work on 1 word files, and the non-working ones include whole sentences.

Here's my best guess.
Looking at the file paths:
1189_working.mp3: mm1.addVariable( "file", "/audio/VMO8cmvDp2U=/1189.mp3" );
1274_not-working.mp3: mm1.addVariable( "file", "/audio/5pmu6YCa6K+d/1274.mp3" );
Comparing the file paths, we see that there is a plus sign in the URL of the non-working MP3.
Plus signs don't work very well in URLs because they were used to represent space characters in legacy browsers. Search these forums for all the problems that users are having with Amazon S3 URLs that have a plus sign in them.
The best thing for you to do, if you have control of the URLs, would be to restrict them to alphabetic and numeric characters, a-z, A-Z, 0-9.