Did you rule out anti-virus email blocking as I suggested? That's the only issue I've had with Database Mail in my environment (We're using McAfee AV).