I remember reading (in the whitepaper) that Radix uses deterministic consensus, as opposed to Ethereum and many other networks which use probabilistic consensus. So, as long as a transaction is valid (it can actually be submitted because the recipient is valid, the amount of tokens sending is valid, etc.) can it ever fail for any reason?
Yes, 99.9% of FAILED transactions get rejected at the Gateway API level.
There are situations when the API thinks that the transaction is OK so it gets submitted to the network just to fail there. An example of how to simulate it - send two conflicting (but different) transactions to different API nodes at the same time. One of them will succeed; another will fail.
However, the failed transactions are not written to the ledger, their status is tracked by the API node that was used to submit it. Here is what it looks like in the mempool_transactions table of the Gateway API: