I write and I edit and I regularly discuss matters of grammar and style. One of my clients recently asked:
"Quick question about which parts to capitalize. The all-seeing Governor, or The All-Seeing Governor ??? Or should I use italics?"
My first thought: is there such a thing as a quick grammar question? :-)

There's some flexibility here, and an author could get away with any of these options: the main thing is to be consistent and make a note of which you go with, in your own style guide document.

1. For one-offs where it is just a description, you could just capitalise Governor (since that's his title/replacement name). "The all-seeing Governor." That's the simplest option.

2. However, if you want it to represent your protagonist's official secret name for him at that point, you would capitalise the prefix, and that's also acceptable. This raises a question. Would you just capitalise the all-, or the second part of the hyphenated word too? All-seeing Governor, or All-Seeing Governor? Well, that's up to you, again as long as you are consistent. Although style guides differ, I'll just go by what my main one, New Hart's Rules, says about how to treat hyphenated compounds:
The traditional rule is to capitalize only the first element unless the second element is a proper noun or other word that would normally be capitalized:

First-class and Club Passengers
Anti-aircraft Artillery

In many modern styles, however, both elements are capitalized:

First-Class and Club Passengers
Anti-Aircraft Artillery
So as you can see, both All-seeing Governor, and All-Seeing Governor would be okay, depending on whether you opted for the traditional or modern style. Pick one, stick to it!

As to italics - used here it would imply a sneer. So you could have a scene where the Governor was talking about omniscient God whilst fumbling for his glasses, and you could ironically italicise all-seeing - it would be a sneer of derision and would have a definite effect. But it isn't an effect you'd want to over-use. In most cases I wouldn't use italics for the words describing the Governor. Like capitals for shouting, it draws attention to itself, and therefore works best and has more effect if used sparingly.

I'll try and cover questions such as this (and some to do with substantive editing and plotting) more often on my blog if they are useful to readers.