Transaction propagation
Does the newly created transaction needs to be propagated to ALL
  nodes in the network in order to be validated?


No. The nodes relay valid transactions to each other. In corner case you can send your transaction directly to miner node. No one will have this transaction until it included in block