So they were actually trying to bring him back, there was superstar hotline rumour about this. I forgot which survivor series it was, I think it was 96', they were trying to get Randy back but instead they got Snuka.
Yep, it was '96. Savage's two-year deal with WCW ended shortly after Halloween Havoc 1996 (where he lost to Hogan but Piper showed up after the match).
They had announced a match for Survivor Series in Madison Square Garden that was Faarooq, Vader, Fake Razor Ramon, and Fake Diesel vs. Yokozuna, Savio Vega, Flash Funk, and a mystery partner.
It was all over the dirtsheets back then that Vince was trying like mad to bring back Savage for that spot. But Savage wanted tons of money, which Vince didn't have because WCW was killing him and he had just thrown everything he had at Bret Hart. Everything fell through and they ended up grabbing Jimmy Snuka to do it.
Savage ended up doing nothing for a few months before finally getting a new deal done with WCW in February 1997.
Everyone likes to act like there was no contact between WWE and Savage ever again, but Savage was actually interviewed for the first episode of Smackdown Magazine when it launched in 2003. It was about Miss Elizabeth's death.
Supposedly, Vince did reach out to Savage once WCW was toast in 2001, but Savage was so unreasonable during the negotiations that Vince felt insulted and never pursued it again.