OK, foi uma razão estupidamente óbvia: temos outro servidor, voltado para o público, que lida com o OWA e similares. Os itens que faltavam estavam na fila naquele servidor.
O Exchange Server primário (no caso da máquina do SBS 2008) foi reiniciado para manutenção no sábado à noite, enquanto alguns itens estavam evidentemente ainda na fila. Meu palpite é que esses itens foram transferidos para o outro servidor quando o SBS foi desativado para manutenção. Este outro servidor não foi configurado para os Conectores de Envio.
Então a resolução era configurar o segundo servidor para usar os conectores de envio - e todos enviados corretamente!