Interesting! Quest-phasing can hide certain zonemarkers, and does so intentionally if the markers refer to something that isn’t accessible/relevant for the quest - but it should not lead to results quite like this. We’re also not seeing this reported widely, so chances are that whatever is happening here is somewhat more unique to the affected characters (hence the suspicion it might have been addon-induced, as those store data on a per-character basis).
Could you please give the following steps a try, to see if they make any difference at all:
-log into the affected character
-type the following commands into the gamechat, one line at a time and each confirmed via the Enter-key:
/console synchronizeConfig 0
/console synchronizeSettings 0
-log out and fully exit the game
-locate and delete the folder that contains your locally stored variables for the character, it should look something like "World of Warcraft\_retail_\WTF\Account\{numbers here}\{Realm-Name}\{Character-Name}"
-start WoW again, log into the affected character once more
-use the following commands:
/console CVar_reset
/console CVar_default
/console synchronizeConfig 1
/console synchronizeSettings 1
/console ReloadUI
This will basically first un-sync the character from any server-stored variables (which addons may have messed with at some point), then purge the local copy of said variables, and finally create new default settings and synchronize those with the server again. If the problem persists past this point a bug report would be highly appreciated!