I have solved my problem, it was my own fault: I had played with our sendmail conguration and changed values for confDELAY_LA, confQUEUE_LA, confREFUSE_LA to 0. The sendmail documentation says for confDELAY_LA: "Default is 0 which means no limit"