Влияет ли увольнение по соглашению на возможность трудоустройства и связано ли оно с Службой Безопасности?

Здравствуйте! Нет, данный факт вряд ли негативно сказывается на принятии решения.

Требуйте от несостоявшегося работодателя письменный мотивированный отказ по правилам статьи 64 ТК РФ

ТК РФ, Статья 64. Гарантии при заключении трудового договора

Запрещается необоснованный отказ в заключении трудового договора.

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

(в ред. Федеральных законов от 30.06.2006 N 90-ФЗ, от 02.07.2013 N 162-ФЗ)

(см. текст в предыдущей редакции)

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

Запрещается отказывать в заключении трудового договора работникам, приглашенным в письменной форме на работу в порядке перевода от другого работодателя, в течение одного месяца со дня увольнения с прежнего места работы.

По письменному требованию лица, которому отказано в заключении трудового договора, работодатель обязан сообщить причину отказа в письменной форме в срок не позднее чем в течение семи рабочих дней со дня предъявления такого требования.

(часть пятая в ред. Федерального закона от 29.06.2015 N 200-ФЗ)

(см. текст в предыдущей редакции)

Отказ в заключении трудового договора может быть обжалован в суд.

Удачного решения вопроса Вам!