Colin, since this was resolved via a support ticket, I wanted to share the resolution so that others in the support community can learn from your experience:
It appears that when this is happening, the 7100 is receiving a REGISTER message from the phone without authentication, to which we reply with a 401 UNAUTHORIZED. The phone should then reply with a REGISTER message with authentication, but we do not receive that. Because we keep receiving the REGISTER messages without authentication, we eventually blacklist the phone. That could be caused by a number of things, I'll order from most likely to least likely:
1) Remote firewall is blocking 401 response to phone
2) Remote firewall blocks REGISTER message with authentication
3) Remote phone receives, but fails to respond properly to 401
4) 401 is dropped somewhere along the path between the 7100 and the phone
5) 7100 does not properly send 401 packet to phone
The problem was eventually traced to a wireless bridge on-site that was dropping traffic.
I went ahead and flagged the "Correct Answer" on this post to make it more visible and help other members of the community find solutions more easily. If you don't feel like the answer I marked was correct, feel free to come back to this post to unmark it and select another in its place with the applicable buttons. If you have any additional information on this that others may benefit from, please come back to this post to provide an update. If you still need assistance, we would be more than happy to continue working with you on this - just let us know in a reply.