Отговор: Правилно е Негово Превъзходителство да се напише с две главни букви, тъй като в случая се титулува висш държавен служител, което изисква стилистична употреба на главни букви за изразяване на специално отношение.
Официален правописен речник (2012), т. 50.1.
[...]