Do all block have to be verified every time a new block is broadcasted?
TL;DR: Each block only needs to be verified once. Upon receiving a new block, only the reference to the parent and the validity of the new block need to be checked.

When one gets started with Bitcoin, the client or mining software will download and verify the blockchain. During this synchronization, each block starting from the genesis block will be verified by the client. This is only necessary once for each block, because new blocks always reference the hash of the preceeding block. 

I.e. when you are trying to verify Block 5, it will contain the hash of it's parent, Block 4. As your client has already verified that Block 4 is valid, and if the hash featured in the new Block 5 matches the known hash of Block 4, it can go straight ahead and only check whether the new Block 5 is valid.