See for me, the Holodeck fell completely flat. Part of it is that I see it as the one great technological leap separating TNG era from TOS era - so it doesn't belong in a TOS-era series. Not in my opinion, anyways. Also, and this is a big complaint, it did nothing for the story. Nothing.
Take it out and you lose nothing but the call-out to Spectre of the Gun, and none of it's referenced again in the episode.
Roddenberry wrote the concept of the "Holodeck" into Star Trek: The Next Generation
, but the concept had already been tested in 1974 in Star Trek: the Animated Series
, where it was referred to as the "recreation room." The holodeck was also discussed in some of the later TOS novels, that took place just after Star Trek VI, with Captain Kirk testing it out.