If not, then why is it often claimed that the blockchain scaling issue is due to the fact that all tx has to be verified by all full nodes?
As long as a mining node found the correct nonce, the tx will be added to the block and the blockchain advances. It does not matter if the tx is not yet verified by some full nodes in the network.
(Yes, it will most probably get verified by all full nodes after it got into the block and the block propagates throughout the network. But this is not relevant as the blockchain already advanced (assuming there is no fork).)