Salida de un mensaje

Saludos. Resulta que tenemos un servidor de correo exchange 5.5 sobre un
windows 2000 y lo que nos pasa muchas veces en los clientes que tienen
windows xp y el office 2003 es que los correos que envian se quedan en la
bandeja de salida un buen rato, como una media hora y luego salen o si
cambias de mensaje o de carpeta salen automáticamente al instante. Otras
veces va bien y no hace nada de esto. A qué puede ser debido? Sera el
servidor de correo por ser un 5.5