The votes must be cumulative, or there would be no solution. Even allowing people to plot and scheme in advance, 500 people could give 10 votes to at most 50 people, and 50 of those votes would be from leavers, so you would need to scheme for 450 people to give votes to 45 people, each of whom voted for a stayer. (Their votes would all cancel.) The same ratios would continue to apply round after round. So votes must be cumulative. The mention of "current vote" also points to this.
Now imagine the round where all the remaining people are going to leave. They have less than 10 votes each - it could be as many as 9. If they are all going to leave, they need to get one or more votes, but they are getting them from leavers, and leavers votes are cancelled. The first person to be voted for can leave, but not whoever that person voted for. You can't get to zero that round.
If you end up with one person, they can't vote for themselves (and if they could and it made them a leaver, it would be cancelled.) If you end up with two people, each with 9 votes, they each vote for each other, one vote is cancelled but the other isn't, and one leaves, reducing you to one that can't leave.
This leads me to conclude they can't all leave. There has to be a stayer whose vote counts in order to send the last leaver away.
That said, I think the best strategy is "line up in one long line and vote for the person in front of you." (The first person votes randomly.) 498 people get one vote, one (the last to vote) gets none, and someone gets 2. After 9 rounds, the majority of folks would have 9 votes. 9 people would have one less from having been last, and 9 people would have more on this round, from being the random ones. Yes, it's possible someone got two twice, and someone got none twice, and someone got none once and twice once, but I don't think the exact numbers matter anyway. If the vote counts are public you could say whoever got two votes has to vote last next time, which will even it out in subsequent rounds.
On the next round, almost everyone gets a vote that puts them over. One gets to leave, which cancels their vote, meaning the person they voted for stays, meaning their vote counts and the person they voted for leaves, etc. Even though everyone was on the cusp, this enables essentially half the votes to count and gets half the people off the island. The rest stay at 9. (ish, there are the last and the randomly-chosens messing it up, but we're not working our way 512, 256, 128 etc so it's ok if we are off by one or two.) You just repeat this until you get to one person left. We weren't asked how to minimize the number of rounds, but I feel this is the way to do it: any other strategy might send someone off with 11 votes (wasting one) or have rounds after the first 9 in which fewer than half the people leave.
