I wouldn't say the seven leagues are clearly better than the boots of the divine messenger. They have paralyzation and death ray resistance and teleport control. If you already have all those intrinsics, sure, they suck donkey. If you have none you probably can't afford not to wear them, movement speed or not. I suspect the boots of the divine messenger would be used more often if players actually got them more often, and if they weren't used to getting the intrinsics on them through another source. Also, you can't always make use of the mobility, and once I realize that I can't, I swap the seven leagues for any kind of armor, especially the boots of the divine messenger. Same if item destruction looms on the horizon; the biggest bane of plain magical items compared to artifacts. (To use seven leagues in the tower, you need a ring of ice; and in the Air Temple, you might as well forget about it.)
I wouldn't exactly mind the change, either - 700 movement is still really, really powerful. Another possible nerf direction though: Seven leagues rely on their blessed nature to be useful. If you make cursing powers more ubiquitous, their value should diminish by quite a bit. On the other hand, that would hit a lot of other items, too...