Rambam (Hil. Beis Habechirah 7:4) says that when a person finishes his service in the Beis Hamikdash, he should walk out of the azarah backwards, so as not to turn his back to the Heichal. The fact that he doesn't say anything about being careful with this during their avodah, though, perhaps indicates that it doesn't matter as much.
We do find that they walked normally, going west to east, in the ezras nashim during the Simchas Beis Hashoevah celebrations (Sukkah 53b), though perhaps then they kept the Nikanor Gate closed so that the Heichal wasn't (as) visible.
Another data point: the kohanim stood on the steps of the ulam to bless the people (Rambam, Hil. Tefillah Uvirkas Kohanim 14:14) - presumably they must have faced east, towards the ezras Yisrael, since birkas kohanim has to be done face-to-face.
On the other hand, Tosefos Yom Tov (to Middos 3:5) cites Raavyah that there were no hooks (for hanging up the korbanos to skin and dissect them) on the west side of the poles set up for this purpose, so that the kohen wouldn't be standing with his back to the Heichal. Similarly, when it came to slaughtering the korban tamid, the kohen doing so would face west (thus standing next to the animal being slaughtered rather than in front of it), and Tiferes Yisrael (to Tamid 4:1) again says that this was so that he wouldn't have his back to the Heichal.
All told, then, it may be simply that they did try to keep this rule when possible, but would vary it if necessary (as with birkas kohanim, and perhaps also when walking around one of the walkways of the altar).