In practice, I would say that it is a very challenging task to determine whether variables are totally independent or not: It is more about the strength of independence. Every time something is "estimated", you'd introduce an additional source of error, and in cases of weak independence the violation may be negligible. Modeling the conditional dependences is basically the idea of Bayesian Belief Networks, and you might find the paper "Comparing Bayesian Network Classifiers" interesting in this context (includes comparisons to Naive Bayes) http://link.springer.com/article/10.1023/A:1007465528199