Honestamente, no tengo experiencia con qmail-send como para decir si es un problema más genérico, pero yo diría que si el problema se da solamente con algunas direcciones, y no por ejemplo con todas las direcciones de un dominio en particular, entonces debe ser debido a las direcciones mismas y no a otra cosa.
Fijate en
http://cr.yp.to/proto/qsbmf.txt y en
http://answers.yahoo.com/question/in...5095437AAKbbVM, el primero explica cómo es el formato de mensajes de error y el segundo menciona que qmail-send a veces no es lo suficientemente inteligente como para determinar la causa del error.
Saludos.