Why do comets appear to have a continuous supply of dust? Comets orbiting the sun have a tail that points away from the Sun, due to the solar wind. 

(Strictly speaking, a comet can have both a type I tail - ion tail, and a type II tail - a dust tail. This question is about the type II tail - the dust tail). 

Now I understand that some of the source of the dust is volatile materials in the comet oxidising due to the comet's proximity to the sun. But surely some of these comets have been orbiting for hundreds of thousands of years (if not millions). Why do they still have unspent fuel? Why are they still dusty? Hasn't all the dust blown off by now?

My question is: Why do comets appear to have a continuous supply of dust?
The rate of loss of mass from a comet is perhaps surprisingly low. A paper The calculation of $Af\rho$ and mass loss rate for comets gives a rate for a "typical" comet at 1.29AU as 153kg/s. A typical comet has a mass of about $10^{13}kg$. Even if the comet is constantly active (and they are not) it would have enough material for over 2000 years. 

In fact comets are only active when the are near perihelion, and they are only near perihelion for a small fraction of their orbit. Put it together and you have the potential for an active life of hundreds of thousands of years.

Eventually, however, comets do run out of volatile substances, at which point they become inactive, and appear as small dark asteroids. An example of which is the object 2015 TB145, which passed the Earth on Halloween 2015. 

Note: not "oxidising", but "vaporising", the ices in the comet are changing into gas, but there is no burning.