В практике письма наблюдается разнобой, но всё-таки справочные пособия рекомендуют писать Его Величество с прописных только при официальном титуловании. В переносном употреблении корректно строчными: его величество случай, его величество возраст, ее величество вечная мерзлота и т. д. Ответ на вопрос № 258707 исправлен.
Большинство словарей рекомендуют склонять только вторую часть: гоголь-моголя, гоголь-моголю и т. д. Напишем главному редактору «Большого толкового словаря» С. А. Кузнецову.
Последние ответы справочной службы
Вот правило: «Названия литературных и научных произведений, произведений искусства, документов, периодических изданий и т. п. заключаются в кавычки, и в них пишутся с прописной буквы первое (или единственное) слово и собственные имена». См. об этом также в «Письмовнике».