There are several theoretical and technical challenges to be resolved in developing effective computational models for mixed-initiative interaction. This paper describes some of the unresolved challenges encountered in the development of a computational model of dialog processing. This model was implemented in the Circuit Fix-It Shop, a spoken natural language dialog system that was experimentally evaluated with eight different users in 141 problem-solving dialogs. From our experiences in developing a system capable of experimental evaluation we have noted at least three difficulties in modeling mixed-initiative interaction: (1) maintaining coherence during an initiative change; (2) choosing an appropriate linguistic form for a response as a function of initiative; and (3) processing silence as a legitimate input and output. Our experiences in dealing with these issues are the focus of discussion in this paper.