[NightKnight]

First of all, I don't think he had the same horse as he had in the beginning. It probably drowned in the flood.

Now, to the question. I think he needed to control his armies against the new threat that the rohirrim composed, instead of fighting Gandalf. I think he knew that Gandalf was stronger, and that he couldn't scare him off. He didn't want to risk a confrontation, at least not without his entire army behind him to invade if he would fail. And being out in the field, fighting against mortal foes, the Fell Beast would be a mighty weapon. A black horse is fine, but it's still just a steed. A huge, stinking, dragon-like creature would be a nice addition to his own terrible power.

I don't think he had any time problems. I can't remember really, and I don't have the books with me, but the Fell Beast probably lurked around somewhere, waiting for its master's call. The Witch-King would only have needed to ride out a bit on the field, maybe to Osgiliath before he could call for it. And I imagine he went pretty straight for king Theoden.