Yeah, they'll have an OEM Toyota built engine alright. That's what they are looking to replace. An OEM Toyota built engine that was neglected, and now needs work or replacement.
I for the life of me will never understand why swapping in a mystery engine with 100k+ miles, is considered a great idea, but a properly rebuilt engine is frowned upon.
It's true there are apparently a lot of hacks out there claiming to be Mechanics, that aren't qualified to rebuild a LEGO® car, let alone a real car. But there are also qualified Mechanics out there that can build an engine to better than OEM specification.
If the block and rotating assembly are in good condition, I wouldn't hesitate to replace the head(s) properly, and drive on with confidence. Instead of installing a used engine, which could be on it's last legs as well.