I ended up building some tooling scripts to do this for stored procedures. It compares the output of the current and proposed stored procedures for all possible

I ended up building some tooling scripts to do this for stored procedures. It compares the output of the current and proposed stored procedures for all possible parameters and displays the differences and the set of parameters that it used. It's not formal verification by any means, but it seemed to work pretty well in practice. It would take forever though. I'd start it and walk away for a couple hours when I wanted a thorough test. But my confidence in correctness and performance gain (it measured perf too) was well worth the effort.