Trouble pairing sensors

My Garmin Edge 25 is giving me fits.

I got it for Christmas a couple of years ago along with the original speed and cadence sensor combo.  The cadence sensor never behaved properly -- it would claim to pair, and then never report cadence values during a ride, even after manually re-pairing.  Speed sensor worked fine, but the cadence value was a constant zero, so I took the Edge off the bike and used my old computer.

Last week I got a new bike and figured I'd try the Edge again, so I got  new combo with Speed Sensor 2.  This time, the cadence sensor pairs fine, but the speed sensor will not pair to the Edge.  It will pair to my phone via Bluetooth, so I know the sensor works.  The Edge 25's software is fully updated but it still doesn't pair

At this point, I've got about a 50% failure rate with various sensors. I'm pretty sure I have a defective Edge, but I'm long out of warranty, and there doesn't seem to be any way to actually contact Garmin to complain anyway.  Any ideas?