Can the helpdesk staff see the SIM number of the card that you are calling from? As if they can see that the call is placed using the old SIM, it would be a good means of auth.
Maybe send a txt to the old SIM, and ask that the user replies with both the old and new SIM numbers. As a scammer won't know the old SIM number, and a naive user can't accidentally approve a swap, as they won't know the new SIM number.
And since Vodafone sent out the new SIM, surely a streamlined process could be developed for that. As Vodafone would already know both the old and new SIM numbers that are associated with that account.