Sugiero que primero trates de identificar los archivos que dan problemas posiblemente tengan algo en común.
Supongo que esos MP3 los tienes grabados en CD, no?
Podrías grabar un disco con MP3 codificados a 320 kbps CBR (es lo máximo posible en MP3) y probar.
Pueden haber varias causas, el reproductor, el propio archivo que no ha sido codificado con ajustes estándar, la marca de CD, tienes que identificar la causa.
Para convertir los archivos MP3 hay muchísimos programas gratuitos, cualquiera debería servirte.
Te sugiero utilizar Foobar2000, es un excelente reproductor y además tiene funciones de conversión desde cualquier tipo de archivo que sea capaz de reproducir.
También puedes usar Xvid4PSP, es un genial programa que sirve para convertir cualquier tipo de archivo multimedia a distintos formatos, es muy versátil y tiene muchas opciones para configurar pero al mismo tiempo tiene configuraciones predefinidas si no te quieres complicar demasiado.