Without seeing code or something more specific than this, we won't be able to help you. 55k entries aren't much at all, so I think that the problem might be with LDAP? Also, upgrade your perl version, it's ancient.
I'd have to agree with AM here ... sounds like you're blaming your hash structure when the LDAP server and/or network latency is your real issue. After upgrading your perl, take a look at Devel::Profile or Devel::NYTProf to try and pinpoint exactly where the code is spending all its time.