Poor high altitude running, burned valves and backfiring under deceleration
are all symptoms of a way-lean condition.  With engine replacements, I would
 begin to think this is either a sensor or exhaust problem.  The exhaust
seems unlikely since I would find it hard to believe that with that kind of
mileage, the exhaust must surely have been replaced.
Not being in any way automotive-computer savy hurts my debugging skills here
but I would still work towards resolving a lean condition.
Mike Pidcoe