A spurious-mode-free variational formulation for the finite element analysis of anisotropic, inhomogeneous dielectric waveguides is derived and demonstrated with examples. Apart from completely avoiding the occurrence of spurious modes, this formulation has numerous advantages including the ability to treat problems including significant amount of loss, the direct solution for the propagation constant at a given frequency and the use of the most efficient representation of the problem, needing only two vector components. This is achieved without losing the sparsity of the resultant (canonical) matrix eigenvalue problem, which only depends on the topology of the mesh used.