The class card says "You earn 1 Imperial and 1 Mercenary villain of your choice."

Is this a one time effect at the start of the campaign or do I earn those villains at the start of each mission so I can choose different villains each time?

I always took it to mean at the start of the campaign.

You earn them at the start of the campaign when you get the 0 XP class cards.

(Otherwise you would earn 2 villains per mission.)

It's start of campaign. Otherwise it would be silly

Earned Villains remain earned for the duration of the campaign. (they're either earned or they are not)