I am an EU citizen, living in another EU country. I managed to vote in the most recent general elections at home. When it comes to the EU elections, I even have a choice: I could vote for MEPs in my country of residence or in my country of citizenship. If voting in my new country was really important to me, I could naturalize and vote in a general elections in my new country.
A requirement to be registered at a new place of residence isn't that unusual. When one moves to another state within the United States, one has to register to vote in that state. Many states require that you live in the state a certain period of time before being able to register to vote, so if you move a week before the election, you are out of luck in your new state. You could be better off voting by an absentee ballot in your old state before you move.
EU citizens generally can vote in municipal elections where they live. Cities and towns also provide services that are supported by tax payers.