Допустим, у нас Мисс Божественность.
Склоняется ли второе слово? Ну, "говорить с Мисс Божественность" или "говорить с Мисс Божественностью"?
Склоняется.
Вы же не говорите «я дал книгу госпоже Иванова» или «пойду в кино с госпожой Иванова»? (Если она, конечно, не госпожа какого-то Иванова...)