the full moon may occur on different (local, not UT) dates

The center of the sun crosses the equator in an instant. The moment of the full moon is an instant. I can see the problem if these instants happen on a Sunday in one part of the world and a Saturday in others, but it should be possible to set the date of Easter based on the timing of these instants in, say Jerusalem. Of course this was probably beyond the capabilities of the early Christians who were setting this up in the first place, but then they didn't have the problem of determining the date of Easter in Kiribati, either.