I married Orla and during the ceremony she left as I said "I do" and now I can't find her. I know she's not in the temple of Dibella because I've spent days in there and haven't seen her.
Orla doesn't ever leave the temple. EVER.
There is a glitch that if you don't talk to your wife right at the end of the ceremony they are gone forever.
And according to all info I've seen, Orla keeps a strict schedule, never ever leaving the temple of dibella. http://www.uesp.net/wiki/Skyrim:Orla
reload your game save from before the marriage, do the ceremony again and catch her before she walks off.
bonus Since Orla lives at the Temple, and never leaves it is good to note : the temple of dibella doesn't have beds.
Orla will not actually leave the temple... So no relocation. Even if she fake agrees and goes through an animation of packing things. It's a bug.
No beds = no sleep AND no sex. So Orla is also one of a few characters that cannot complete the "lover's favor" quest.