Does doping always increase the conductivity of a semiconductor?
Is there any circumstances when conductivity decreases if a dopant is added (whether p-type of n-type?).


Yes. Consider compensation doping. 

Suppose silicon is initially doped with donors, making it n-type. 

If you then begin to dope with acceptors, this will not immediately create a p-type material. Instead, the acceptors will provide locations for free electrons (provided by the initial donor dopant) to be captured, reducing the electron concentration, and thus the conductivity of the material.

If you can match the acceptor concentration very closely to the donor concentration, you can produce material that is very near intrinsic in its behavior.  (Matching the concentrations is difficult in practice because the different dopants have different diffusion coefficients, etc.)


  But does this equation always hold true? [\$\sigma = qn\mu_e + qp\mu_h\$]


This is still true. This just says the conductivity is proportional to the carrier concentration. It doesn't say anything about what dopants were added to achieve those carrier concentrations.


  What happens if a dopant is added which has a large binding energy to the lattice. Surely that'll decrease the conductivity!?


Here, I'm not clear what you're asking about.

The binding energy of the dopant to the lattice doesn't have much to do with its contribution of carriers.

If you're talking about a dopant that requires a large energy to ionize, it has little effect because that means the captured state energy levels are "deeper" in the band gap, so less likely to be occupied, than for a dopant requiring little energy to ionize.