What about the ability of nodes and miners to decide whether transactions are valid or invalid? If they can't do that, wouldn't it be possible to spam the blockchain?
No - The miners don't validate the txn. They simply take some inputs with random values and give it to some outputs with random values (as far as they know). All the validation is done by the users.
You can't cheat the system, as the receiver would not accept a txn that had an invalid history as valid, and since the txn would be mined as usual whether it was valid or not, since the miners can't tell (and mine the txn regardless), if you did try and cheat all you would do is lock up the funds in a spendable-yet-invalid output. That no one would accept as payment.
The miners are still used to prevent double spends. They won't let you spend the same output twice, but they won't know how much it is for.
..
The miners would need to be paid a fee though, and as you say, that would need to be un-hidden as you don't know which miner will find the block.. Or some new as-yet-un-envisaged system..