"Либо это заголовки (mp3 заголовки) каждого отправленного пакета", насколько я знаю, у формата MPEG нет общего файлового заголовка, есть заголовки отдельных кадров. Думаю проблема в задержке записи/ считывания файла. Есть ли в NAudio возможность сформировать mp3 в памяти без записи в файл?

 Вообще я считаю, правильное решение должно основываться на DirectShow и использовать:

-свой исходный фильтр, получающий данные с аудио-выхода,

-любой имеющийся фильтр-компрессор MP3 потока,

-свой фильтр вывода, отправляющий данные на сервер.

Реализации DirectShow под .Net есть, я не знаю, позволяют ли они создавать свои фильтры (а это здесь похоже понадобиться)

Есть идея. Что если вместо

            var fileBufMp3 = File.ReadAllBytes("out.mp3");
 
            //шлём на сервер
            netshout.SendSteam(fileBufMp3);

сделать так:

int buffer_size=100;
int result;//amount of bytes actually read
byte[] buffer;//bytes read from file
byte[] send_mas;//bytes to send into server
FileStream fs=new FileStream("out.mp3");
using(fs){
 while(true)
 {
  buffer=new byte[buffer_size];
  result=fs.Read(buffer,0,buffer_size);
  if(result<=0)break;//end of file
  send_mas=new byte[result];
  System.Array.Copy(buffer,send_mas,result);
  //шлём на сервер
  netshout.SendSteam(send_mas);
 } 
}          

параметр buffer_size нужно будет опытным путем подобрать оптимальный

вот тут нашел: http://stackoverflow.com/questions/19058530/change-format-from-wav-to-mp3-in-memory-stream-in-naudio

у LameMP3FileWriter есть конструктор, который первым аргументом принимает Stream. можно ему попробовать скормить MemoryStream:

public static byte[] ConvertWavToMp3(byte[] wavFile)
        {

            using(var retMs = new MemoryStream())
            using (var ms = new MemoryStream(wavFile))
            using(var rdr = new WaveFileReader(ms))
            using (var wtr = new LameMP3FileWriter(retMs, rdr.WaveFormat, 128))
            {
                rdr.CopyTo(wtr);
                return retMs.ToArray();
            }


        }