Anything that causes incomplete combustion, i.e. compression, ignition or fuel mix problems, will dent mpg.
Compression or ignition problems are more likely to come on suddenly, and are more likely to cause noticeable misfires and rough running - although two plugs per cylinder could mask any spark issues. Vacuum leaks can go unnoticed as it can just lean the mixture off a little. If you are running out of ideas, it's worth having a squirt around the inlet manifold with some carb cleaner or easy start, see if you can affect the idle speed.
Have you had a plug out of every cylinder, are they all the same colour? You're doing the right thing trying rule stuff out, but as Jocko says earlier, it pays to check the common problems like brakes binding, good spark, etc..