I don't think it would be cheesy to have an NND attack, with the defesnse being solid, depending on the special effect. If your villians become desolid by going to the ethereal plane, for example, then it would seem to make sense that your mage could develop an attack that would work against things on the ethereal plane only.
You might also consider AP to lower defenses, or the power Find Weakness, if your GM will allow it.
Of course, with all your character's knowledge skills, I would think that your GM would give you some sort of hint on how to deal with your villains. (In fact, it's possible that your GM is thinking that he gave you a situation in which those skills are useful, and he's waiting for you to tell him that you'll use them ...)