You should be validating all protected headers, in much the same way as border patrol should reject a crayon drawing of a passport.
JWS (and JWT) standardized interoperable parameters and what they mean, but applications are supposed to standardize how they are used.
An integrity protected message used as part of a transaction, one used to represent user state, and one used for document archival are going to have dramatically different requirements for verification metadata.
Similarly, a signed message issued by a single site vs one meant for use across a federation will have different requirements.
This is the #1 misconception of JWS/JWT which has led to people mislabeling it as insecure. They are only using the half that defines what fields mean, and ignoring application-specific instructions on if they are supposed to accept and how they are supposed to process those fields.
The point of input in any case is that you are going to validate it and then process it. Any input that isn't validated should not be trusted, even in the most benign scenarios and triply so in security relevant contexts.
Someone specifies the `null` algorithm? Reject the token outright, someone's trying fudge things. Someone specifies the `blahwhatever` algorithm that you actually trust yourself. Sure, try that algorithm, if results come back valid, all is good. Results come back bad? Reject the input without trying any of the other 19 algorithms you support and trust on the input.
As you can see here, the purpose of the field is to make it easy to validate the token without having to try all the algorithms that you might support. If you support 20 algorithms for something, you don't want to have to try all of them. But you do have to know which algorithms you trust. It's really not different from an SSL negotiation. You know which algorithms you accept/support, the other side knows what algorithms it accepts/supports. If you can't find one both of you support: tough luck!
The existence of algorithm confusion attacks shows that it's not nearly as simple as just saying "Reject 'null'". It's a complete minefield, and the fact that the JWT scheme punts that complexity and "make sure you hold it correctly!" onto the application is bad.
Had the algorithm been standardised to a single value out of band (ie. in the spec), that would have squashed a whole load of vulnerabilities.
For example: simply take a valid identity's public key, and use it as the secret to forge a token with alg=hs256. A service receiving this token will use its copy of the public key (by key id) to verify the signature, but because it's being told that it's an HMAC-signed token, will construct an HMAC.
Of course this HMAC will verify correctly because both you (the attacker) and the server hold the same public key used. And now the server thinks its a legitimate JWT because the signature is valid.
Mixing symmetric and asymmetric cryptography types in the same message scheme is just one of the many ways in which JWT is a bad idea.
I really don't think this is an intrinsic problem at all.
I've written JWT-parsing code and it looked for a local public key if it got an RS-algorithm and a local secret if it got an HMAC algorithm. It would be an insane implementation to treat either of them as the other.
What's the purpose of the algorithm field in the header if clients shouldn't trust it? It's "input", after all...