Holy crap, I can't find the strap that I had paired with the fenix and edge. I tried a fresh battery in my other, newer strap that has worked before, but it wouldn't detect on either device after repeated attempts, including wetted up, briefly jogging, etc.
Tried searching, Garmin link was useless for to getting it to work.
Youtube video said to take out the battery, short the battery connections for 5-10 seconds and try again.
It worked as promised!