I did some digging into the issue causing islands to be lost. Here's what I found.
We lost data about a lot of islands due to a bug, causing these islands to be without an owner. Now, when a new player creates a new island, there is a chance that the new island spawns on top of an island we lost data of, thereby effectively griefing it and stealing it from the previous owner. There is no easy way for us to assign the lost islands back to their original owner.
That said, there might be a way to restore some island data. This however would be a lot of work to do and would still leave us with an all in all buggy island protection system.
Overall, a server wipe including the adoption of a different island protection system seems like the best way forward.