That being said, it doesn't seem like it would be hard to have a national voter database that shows each voter and where they are registered, with the ability to notify districts when someone shows up elsewhere, combined with a national registry of death certificates.
Is the eligibility wrong though?
There has been a sort of reverse Gerrymandering [1] in the UK where voters are instructed where to vote to have the most effect, people with second homes (which can include students but otherwise would seem to be exclusively rich people) might qualify this way in the UK.
Generally this indicates to me the need for electoral reform. But perhaps tighter regulation about where one may vote (restricting eligibility when one is eligible elsewhere) is also needed in some places?
If I don't update my driver's license, the DMV wouldn't have my new address either.
If I move in with roommates and I pay my roommate for utilities, the utility company wouldn't know my new address either.
Just a few reasons why it is a hard problem.
I'm not sure why it has to be such a hard problem? If I file taxes in tax year N at a given address, and then file taxes in tax year N + 1 at a different address, then it's pretty clear that I am no longer a resident and should be removed from voter rolls. I'm aware that this doesn't cover everybody, but if you combine a few different such datasets that the government already keeps track of people moving, then you should be able to easily assure that most stale entries are removed in timely (<1 year) fashion.