Those delays can be caused by greylisting.

http://en.wikipedia.org/wiki/Greylisting