В орфографических словарях зафиксировано написание с прописными буквами, склонение второй части необходимо, например: исполнила партию Царевны Лебеди, думаю о Царевне Лебеди, идет рядом с Царевной Лебедью.

Если авторские слова, стоящие после прямой речи, представляют собой отдельное предложение, то они начинаются с прописной буквы:

– Я же говорила. – Гордая мама подпёрла бока руками.

– День получки! – Сторож похлопал себя по карману.

Обратите внимание: второе предложение построено неудачно, т. к. глагол заметила воспринимается как глагол говорения.

Ситуация, в которой авторские слова, стоящие после прямой речи, представляют собой отдельное предложение, представлена в примечании 2 к параграфу 48 справочника по пунктуации Д. Э. Розенталя. Согласно рекомендации, авторские слова в этом случае начинаются с прописной буквы:

— Карин, ты бы не пила больше. — Я с тревогой посмотрела на подругу.

Первая часть этого бессоюзного сложного предложения представляет собой синтаксический фразеологизм (нечленимое предложение), часто оформляющийся в отдельное высказывание, как можно сделать и в данном случае, сравним: Что поделать! Никто не научил меня этому!.. Будучи включенными в бессоюзное сложное предложение, синтаксические фразеологизмы обычно отделяются запятой: Что поделать, никто не научил меня этому.

В данном случае необходимо понимать, в какой функции и в каком значении употреблено слово ну. Оно фиксируется в словарях как междометие, выражающее определенные эмоции, и как частица. Междометие требует отделения запятой (часто оно вообще представляет собой отдельное высказывание), частица — не требует. См. параграф 108 «Полного академического справочника» под ред. В. В. Лопатина.

Правило, которое Вы цитируете, никто не отменял. Но есть еще одно правило, связанное с оформлением прямой речи: если авторские слова, стоящие после прямой речи, представляют собой отдельное предложение (не содержат глагола речи), то они начинаются с прописной буквы:

— Скорей, загорелась школа! — И он побежал по домам будить людей.

Возможно, Вам встретился подобный вариант оформления?

В разделах, посвященных вводным словам, справочниками регламентируется лишь постановка запятых, в редких случаях — тире. Вместе с тем постановка двоеточия после вводного слова кстати в начале предложения не выглядит ошибкой, поскольку в таких случаях слово играет роль текстовой скрепы и, вообще говоря, может быть оформлено как отдельное предложение, сравним: Кстати! Мне вчера приснился вещий сон!

Мне всегда везёт с ними — это отдельное предложение, грамматически не связанное с остальными частями высказывания (они образуют сложноподчиненное предложение Я договорился с подрядчиками, чтобы остатками асфальта залатали ямы). Иначе говоря, это вставная конструкция. Наиболее уместны в таком случае скобки: Я договорился с подрядчиками (мне всегда везёт с ними), чтобы остатками асфальта залатали ямы.

Пунктуационное оформление вставки соответствует правилам. Правда, судя по контексту, здесь имеет место еще и передача прерывистой речи. В этом случае уместно использовать многоточие: Там было много этих... — о, точно! — этих опоссумов. Другой вариант состоит в том, чтобы оформить междометное высказывание не как вставку, а как отдельное предложение: Там было много этих... О, точно! Этих опоссумов.

Нужно руководствоваться словарными рекомендациями:

Орфографический словарь

Большой толковый словарь

Русское словесное ударение