I read up on him here in the beastiary and it was usefull information.
I started out by fighting my way up to 6b, then I killed bats to clear the watery area. Once all the bats/vampires were down and the Shadowed Necro was down I went back to 6a and looked for the Icy Shadow that had a pet and black cuffs (all the others have a white cuff at the end of their sleeves). Killed Icy Shadow, ran back up to 6b (had to kill some more Shadowbeast Guards along the way) and found ValSera standing in the water waiting for me. Killed ValSera with 61 War + 52 Shm and viola! Got key for lvl 7 and the section of draconic tome. Pretty easy it seems.
As for why others were unlucky/unable to spawn him...I cannot say. I speculate that it was somthing buggy with the game.
Hope that helps.