Did "all the troubleshooting" include checking the IPv6 settings on your Mac? They need to be set to Link Local Only.
If you have an iPhone or iPad, have you checked to see whether the Time Capsule will appear on the iOS device?
If the Time Capsule still will not appear in AirPort Utility, then the cause of the issue is deeper.
Apple had an issue with Back to My Mac that was affecting a number of users, which caused AirPorts and Time Capsules to disappear from AirPort Utility, although the Internet connection still functioned correctly. This might be affecting you.
A firmware update was issued to take care of this, but unfortunately since you cannot "see" the Time Capsule at this time, you can't check to see what firmware version is installed on the Time Capsule. Do you happen to know what version of firmware is installed on the Time Capsule?
It may be necessary to perform a Hard Reset on the Time Capsule to get it back to default settings, and then set it up again. But, you would not enable Back to My Mac on the Time Capsule until you have verified that the most up to date firmware version is installed.