I decided to take a break from Skyrim and reinstall Morrowind for the first time in years. Unfortunately I can't remember where to buy the mark and recall spells, and no one I've checked yet has them. Is there anyone who is guaranteed to carry them, is it random, or is it level based?
There are several vendors who will sell you Mark and Recall, one that I remember being fairly easy to find is J'Rasha in the Foreign Quarter of Vivec.
Sirlonwe at the Vivec Mages' Guild also sells both halves of the spell, although I can't recall if there are any requirements for her to teach it to you (such as being a member of the guild).
Balmora's temple also has a pair of NPCs (Llarara Omayn and Llathyno Hlaalu) who sell the two halves of the spell, and Balmora's one of the earliest towns you're likely to visit.
If you're quite far from Vivec or Balmora and/or would prefer another location, there's a complete listing of all the NPCs who will sell you these spells on the UESP Wiki.