Rim shot? Goes badly out of true at medium tension
Yes.

Once the rim has taken a set (ie it is really bent), you can only true it so far with tensioning spokes.  Too much tension will strip nipples, or can even snap spokes outright.

You did right by backing off all spokes till they're all loose.  Then use brute force to "straighten" it once you've identified the areas of the rim that are out.  A large flat surface helps, or another rim that is known to be true.  Flip things over and over, use elimination to identify the bad spot/s.
The straighten the curves.  This is sometimes done using a street drainage grate as a lever or plain old stomping, like this:



As long as you can pressure the high and low spots and make it "flat" then it could be trued from scratch.

If its really dead, then its dead.



However you say the rim looks fairly flat with the spoke tension all slacked off.  That's puzzling, and I'd recommend a close look at the rim nipple holes.  Could be some of them are a bit softer metal than you might want, and they're moving under pressure.  Also check the hub end of the spoke to see if there's any damage to the flange.

Unless there's something really good about the wheel, it can suck up a lot of time and still come out with a sub-par wheel.

I have about 4 spare wheels for various bikes - as you come across good ones, then keep them.  



I have a seriously dodgy wheel where one spoke has no tension at all.  It goes out of true if I so much as finger tighten that one spoke.  Its perfectly ride-worthy for me, but I'd not put it on someone else's bike without fully sharing the problem.   As a rim brake wheel, true is more important than spoke tension.

Separately, I've wasted 4 hours trying to true up a front wheel for a give away.  In the end I swapped the hub and spokes to another rim, and got the assembly and truing all done perfectly in 30 minutes.