[Radek]

Perhaps, a silly question but I haven't meant it as an offence. Are you searching the lich at the right place? The lich isn't in the room with the level 12 lock. The lich is in a locked room near the entrance to the area behind the dark legionaries. The key to this room is in the trapped room with traps spitting the Face of Death spells. The room with the lich can also be entered from the room with the level 12 lock but only after completing the lich quest. The door is locked now.

Notes:
1. I am always finding the lich where it should be. The patch should not be guilty: AFAIK, people playing the patched game haven't experienced your problem.
2. You need not the staff if you are able to cast the Vanish spell. Go to the shrine, climb one of the steep red ramps at the sides of the entrance, and cast Vanish. You will occur behind the lock and you will be able to enter the shrine. Place a portal there (I mean behind the lock and outside the shrine). You will be able to teleport to your portal from everywhere in the wilderness.