As @diedrichg pointed out this thread is getting long, so I wanted to create a long summarize some of the solutions listed above.
Bad Matter over Thread Device
@mobile.andrew.jones
Some devices might not have the same level of effort or quality as others. Nanoleaf Essentials have/had known issues with some of their early devices. Try other devices if you can.
Personally I found the Eve device built for Matter over Thread to integrate excellently
Work on a single vLAN
I would suggest avoiding working across vLANs as much as possible. There are a lot of ways to have multiple vLANs talking to each other, but very few manufactures properly implement mDNS support/forwarding. I moved all my IOT devices, including my HA host onto the same vLAN, and whenever I need to add a new device I switch over to do so. It’s annoying but prevents so many inconsistent issues.
Having multiple access points shouldn’t be an issues as long as they are all on the same network/vLAN. I’ve heard tail that some repeaters don’t properly support IPv6/mDNS, which ended up causing some people a headache. So it might be worth turning any off while troubleshooting issues
Ensure IPv6 is enabled on your network
IPv6 is required for thread to operate correctly. Below are a few guides.
Please note, you may need to make differet selections based on if your ISP is providing an IPv6 address for you or not. You can check your current IPv6 address here: https://test-ipv6.com/
General:
UniFi:
Unifi no public IPv6:
Reset Thread Credentials on Your Mobile Device
Big thanks to @HARookie since this is what got my mobile phone working again.
Android:
-
Clear all cached data from Google Services
Keep your device & apps working with Google Play Services - Google Play Help -
Sync thread credentials
Now in the HA companion app sync the credentials with your device
Settings->Companion App->Troubleshooter and call “update thread credentials”
Apple:
Sorry I have no idea, 
Check below to see if anyone posts directions below
Nuclear option: Directly add Matter Devices
Quick note: I’ve done this for several devices. I have not found any negative effects from it so don’t hesitate to at least try it if you’re at wits end. I call it “Nuclear” more as a joke, but it is an approach that is against the ease of use idea of Matter.
The TL:DR is add the devices via console commands using a Bluetooth connection from the HA host itself. Programing experience is recommended
Troubleshooting Tools
mDNS
@mobile.andrew.jones
Matter over Thread uses mDNS to broadcast it’s availability, so any tools to help view mDNS on your network may help.
On Android “Service Browser” worked well for me. On windows “All My LAN” is free on the Windows store.
Matter Network
The Matter Server add-on recently added a UI to view the matter network. Check it out Settings > Add-ons > Matter Server > Open Web UI
It’s not super helpful yet, but gives a bit more insight into already added, or disconnected devices
Additional Resources:
Some extra reading material if you want to dig into how Matter over Thread works
