В русском языке аббревиатуры и несклоняемые существительные иноязычного происхождения (не обозначающие живых существ, то есть неодушевленные, ср. слова на -и: сулугуни, салями, кольраби, цукини) обычно приобретают те родовые признаки, какими обладают опорные слова. В случае с аббревиатурами эта закономерность проявляет себя наиболее последовательно. Нагляден пример аббревиатур, образованных на базе сочетаний со словом институт (НИИ, МАИ, ИАИ и т. д.), центр (НЦБИ — научный центр биологической информации): они употребляются как существительные мужского рода. Иноязычные аббревиатуры не исключение: Би-би-си — существительное женского рода (по слову корпорация); у существительного среднего рода ЦРУ есть опора в виде существительного управление; существительное мужского рода сиди (от СD) наследует грамматические признаки слова диск. В печатных изданиях можно встретить обороты типа базовый / функциональный / мощный / удобный API. Они свидетельствуют о том, что иноязычная аббревиатура API (с опорой в виде слова интерфейс; от англ. Application programming interface) согласуется с прилагательными по образцу существительного мужского рода. Вместе с тем констатируем: в текстах запечатлены и сочетания, в которых аббревиатура API предстает как существительное среднего рода; ср. мощное и удобное API.

Да, в подобных двухчастных заголовках ставится двоеточие. Оговоримся, что в справочнике по пунктуации Д. Э. Розенталя приводятся только примеры заголовков, состоящих из форм именительного падежа существительных, типа Многоэтажные улицы: спасение или бедствие? Между примерами из справочника и Вашим примером имеются и смысловые различия. В заголовках из справочника первая часть называет общую проблему, место действия, лицо, а вторая — содержит конкретизацию названного в первой части. В приведенном Вами случае в первой части заголовка приводятся чьи-то слова в форме прямой речи (хлесткая фраза, призванная привлечь внимание к новости), а во второй части поясняется, кто и при каких обстоятельствах сказал эти слова, и как раз это пояснение является новостью. Впрочем, полагаем, правило об оформлении двухчастных заголовков вполне можно распространить и на примеры вроде приведенного Вами. 

Запятые не нужны.

Предложение требует правки, например:

Неправильная запись должна быть аккуратно зачеркнута, а рядом должна быть внесена новая запись, заверенная ответственным лицом.

Запятая после зачеркнута не нужна. Обратите внимание, что запись должна быть записана — некорректно, и одно из этих слов следует заменить.

Если речь именно о типовом названии, а не о наименовании конкретного самостоятельного подразделения, то верно написание со строчной буквы.

Да, запятая нужна.

Употребление строчной буквы корректно. С прописной слово министерство пишется только как первое слово полного официального названия.

Скорее, это однородные сказуемые, соединенные союзом "точно". Сравнительными оборотами принято называть обстоятельства сравнения.