As soon as you get the Pokemon, if you intend to EV train it.
Every time is levels up after a battle, the Pokemon would have received some EVs. Since it received EVs, the 100 is already being decreased; if you defeated a Volcarona, you'd get 3 SpAtk EVs, therefore the Vitamins work for the next 97 EVs for SpAtk. So if you are levelling up by battling Pokemon, use them as soon as possible to use them to their full potential. But if you are levelling up by methods that don't involve EVs (Day Care, Rare Candy, etc.) use them as soon as you begin to level up on real Pokemon from the wild/from a NPC.