Корректно: не замерзшая еще речка. 

С полными формами причастий отрицание не пишется раздельно:

а) если при них имеются зависимые слова, напр.: человек, не гнушающийся никакими средствами; не ведающий, что творит; не заботящийся о пропитании; друзья, не видевшиеся много лет; не подтверждаемая фактами версия; не признанный современниками гений; не опознанный наземными службами объект; не связанный обязательствами; не обязанный подчиняться; не растроганный её слезами; давно не стиранное платье; с весны не крашенная крыша;

б) в составе конструкций с противопоставлением или конструкций, усиливающих отрицание, напр.:

Это не законченная работа, а какие-то наброски; не знающий, а лишь догадывающийся; не воюющие, а мирно соседствующие страны; не уважаемый — любимый; отнюдь не успокоенный, нимало не смущённая, нисколько не обрадованный, никем не замеченный, никогда не унывающий, никем не любимый.

К чему относится отрицание не – к прилагательному (т. е. об оружии сообщается, что оно является нелетальным) или ко всему сочетанию (т. е. о чем-либо сообщается, что оно не является летальным оружием)? Если не относится к прилагательному, верно слитное написание, если ко всему сочетанию – раздельное.

Возможно слитное и раздельное написание. При раздельном написании подчеркивается отрицание.

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

Раздельное написание связано с тем, что здесь отрицается понятие, а не создается новое. Отрицание относится к обоим словам (слава богу, что она не является закомплексованной обиженкой).

Слитное написание предпочтительно, но допустимо и раздельное, если надо подчеркнуть отрицание.

В обоих примерах возможно и слитное, и раздельное написание. Раздельное написание подчеркивает отрицание.

Частица не во второй части предложения выражает отрицание: "учреждений, куда его не звали, уже не осталось".

Сложность в том, что вторая часть формально (в том числе из-за частицы бы) похожа на придаточные уступки, которые пишутся с ни (например: Куда бы его ни звали выступать, везде его ждал успех). Однако это придаточное определительное.

Возможно как слитное, так и раздельное написание. При слитном написании утверждается нереальность, при раздельном – подчеркивается отрицание (отрицается реальность).

Возможно как слитное, так и раздельное написание. При слитном написании утверждается неуместность, при раздельном – подчеркивается отрицание (отрицается уместность).