We've got some goofiness in the Domino Directory (also referred to as the Name and Address Book or NAB) that's causing corruption and resulting in odd routing issues. I've updated the nightly recycle jobs to include tasks that should reduce (or remove) that corruption.