XBee encryption & node discover problems

First some info on my devices:

ATVR
10E2
ATVL
ERROR
ATHV
1742

If I enable encryption with ATEE and use a 10-character crypto key, my ATDN and ATND requests start to fail. If I run ATND more than once, I will sometimes get multiple responses from each node on the second or third try. This suggests to me that the devices are lagging significantly when encryption is turned on. Port-to-port serial communications don’t seem to be any slower with AES enabled, so I’m at a loss.

Do you have any suggestions?