СЮГ> Я придумал одно решение, но оно мне не очень нравится. Но, похоже что другого просто нет...

Поскольку очередь задач была одна, то одновременно нельзя было отправить более одного сообщения каким бы малым не было время его отправления. Разбил очередь задач на несколько параллельный очередей (96 штук). Каждый recipient привязан только к одной из них (связывается в конструкторе раз и навсегда). Теперь одновременно с большой вероятностью можно отправить несколько сообщений -- столько сколько процессоров в машине (несколько сообщений можно отправить получателям привязанным к разным очередям, чем больше очередей, тем больше вероятность "параллельности"). Да появились дополнительные накладные расходы, но они не очень большие, зато производительность теперь растет линейно с количеством процессоров. В итоге имею 18-27 миллионов сообщений в секунду на Athlon 64 X2 2.21 GHz. На четырёхядерном значит ожидаю, что-то под 40-50 Мегасообщений/сек, но у меня его нет, проверить не могу.