We had the same problem here. What worked in our case was:

Traffic to port 113 (identd) was blocked. Because the server didn't give any
response at all there was a time-out to which we were waiting.  Opening up
the 113 port significantly speeded things up. Even when no ident-deamon was
running on the system. (it now gets an immediate no deamon running msg, and
can go on with it's processing instead of having to wait for a time-out)