Как прошлый работодатель может влиять на возможность прохождения службы безопасности при поиске новой работы?

Не может, незаконный отказ может быть обжалован в суде

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

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

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

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

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

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

Добрый день! Если оснований нет, то юридически работодатель не сможет ничего сделать официально, при этом он может отказаться выдать Вам положительный отзыв или характеристику, если их потребуют на новой работе.