My problem with Xaldin was that I kept going into Anti-Form which was so unbelievably frustrating as he inflicts 75% more damage to me >< But I usually ran all the way to the other side of that bridge thing, and I eventually got him...
I got Sephiroth at 79 with Oblivion if I remember... It took me at least 30 tries ><;;;