Is it true that the more nodes would reject a certain transaction, the higher fee will be needed to get it into a block? Hence making it harder to spam?

Nope.