Indeed, sir. I discovered that my 30-watt soldering iron wasn't up to the task of heating up the (relatively) big relay plates; I could melt the solder a bit with just the iron, but adding soldering braid onto the joint transferred too much heat away.

DJ confirmed I was on the right track by upgrading my iron ($17 for an 80-watt, thanks Microcenter!) and getting a $4 solder sucker, I had the old relay off in 10 minutes and the new one on in 1!
Now the CEL stays off, I can hear the hair-dryer secondary air injection roar on startup, and I passed the IL emissions test. thus we were able to get a renewal sticker for the plates and are fully legal once again.
My thanks again to DJ and posters in this forum for the right troubleshooting steps and repair advice.