Правильно: «был выпущен 21 сертификат». 

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

Запятая не требуется.

Приведенные Вами примеры - это примеры словообразования, а не склонения.

Дело в том, что словообразовательная морфема -ск- представлена в русском языке тремя вариантами (морфами).

Морф -ск- выступает в позициях: а) после губных и зубных согласных (находящихся перед данным морфом, за исключением |н| - |н'|, в позиции фонологического неразличения твердых и мягких), а также после |н|, |р|, |л'| и |j|, в том числе после различных сочетаний согласных, без ограничений: соседский, сербский, лермонтовский, океанский, организаторский, эскимосский, ассистентский, марксистский, шефский, майский, февральский, пермский, монмартрский (от топонима Монмартр); б) после согласной |ц|, фонетически ассимилирующей первую согласную морфа -ск-, что передается орфографически как -цк(ий): казацкий, немецкий, елецкий; в) после заднеязычных и шипящих - только в образованиях, мотивированных топонимами и этнонимами (моздокский, лейпцигский, палехский, нивхский, палангский, парижский, угличский, чешский, быдгощский), фамилиями на -ич (мицкевичский) и в словах герцогский, шахский, мужской, коллежский; г) после |р'| и |н'| - в словах сентябрьский, октябрьский, ноябрьский, декабрьский, июньский, деньской (в сочет. день-деньской); д) после |л| и |н'| - в некоторых прилагательных, мотивированных нерусскими топонимами: ямалский, кызылский, халхинголский, тянь-шаньский, пном-пеньский; е) после гласных - только в некоторых прилагательных, мотивированных несклоняемыми топонимами, преимущественно эстонскими, и этнонимами: бордоский, ватерлооский (Ватерлооская битва), майяский (майя - ⁽группа родственных индейских племен в Центр. Америке⁾), тартуский, раквереский, чарджоуский.

   Морф -еск- (фонемат. |a₁с₂к|) выступает после шипящих в образованиях, мотивированных нарицательными сущ.: супружеский, купеческий, юношеский, товарищеский. При этом на месте шипящих в основе мотивирующего слова могут выступать как шипящие (трюкач - трюкаческий, ханжа - ханжеский, юноша - юношеский), так и другие фонемы (друг - дружеский, князь - княжеский, логика - логический, купец - купеческий, ребята - ребяческий, монах - монашеский).

   Морф -овск-, орфогр. также -евск- (фонемат. |ов₁с₂к|), выступает после согласных (кроме |к'|, |г'|, |х'|) в прилагательных, мотивированных: а) некоторыми нарицательными сущ. муж. р. I скл. - немотивированными и с суф. морфами -ик, -их, -ец: воровской, шутовской, отцовский, дедовский, жениховский, стариковский, портновский, борцовский, чертовский, бунтовской, банковский, кремлевский, съездовский, августовский; особенно тяготеют к сочетаемости с морфом -овск- основы на -ик и односложные основы: нов. битниковский; окказ. сочельниковская елка (Возн.), фрицевская телега (Нагиб.), сейфовские ключи (газ.); б) личными именами муж. р. I скл., а также фамилиями и прозвищами различных типов склонения: Пётр - петровский, шекспировский, капабланковский, горьковский, геркулесовский, дарвиновский, гойевский, жюльверновский; в) топонимами различных типов склонения: Днепр - днепровский, Орёл - орловский, Массандра - массандровский, Клинцы - клинцовский, Нагорье - нагорьевский; г) аббревиатурами - нарицательными и собственными (профорговский, детсадовский, уралмашевский); д) однословными названиями учреждений и предприятий, партий и других политических группировок, журналов и газет, спортивных обществ, кораблей и т. п., принадлежащими к различным типам склонения: "Калибр" (завод) - калибровский, Бунд - бундовский, "Искра" - искровский, "Зенит" - зенитовский, "Аврора" - авроровский; сравним: шахтёр (лицо, нариц.) - шахтёрский и "Шахтёр" (спортивное общество) - шахтёровский.

См.: Русская грамматика / Под ред. Н. Ю. Шведовой. М., 1980. Пар. 631.

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

При этом см: 

Справочник по русскому языку. Пунктуация. Д. Э. Розенталь//РАЗДЕЛ 11 Знаки препинания при оборотах, не являющихся придаточной частью сложноподчиненного предложения, § 42.3

Здесь сказано: 

Запятыми выделяются или отделяются сравнительные обороты с союзом как в случаях, если оборот начинается сочетанием как и: К Москве, как и ко всей стране, я чувствую свою сыновность, как к старой няньке (Пауст.); В её глазах, как и во всём лице, было что-то необычное; Дети, как и взрослые, должны быть приучены к соблюдению правил общежития; Как и на прошлогодних соревнованиях, впереди оказались спортсмены Российской Федерации.

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

Тебя ж, как первую любовь, России сердце не забудет! (Тютчев). 

Попробуйте произвести здесь подобную замену — ничего не получится. А в разбираемой конструкции это происходит безболезненно:

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

К Москве и ко всей стране я чувствую свою сыновность;

В ее глазах и во всем лице было что-то необычное;

Дети и взрослые должны быть приучены…

При этом оттенок присоединительности (то есть добавочного попутного сообщения) и отождествления пропадает — следовательно, именно этот оттенок вносится союзом (или союзным оборотом) как и.

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

Можно полагать, что во всех этих случаях мы имеем дело с результатами компрессии (сжатия) исходной сложноподчиненной местоименно-соотносительной конструкции отождествительного типа (правда, при «восстановлении» такой конструкции приходится менять порядок слов):

Она не ответила мне так же, как и своего движения по комнате не прекратила …

Я чувствую сыновность к Москве так же, как и ко всей стране [чувствую];

В ее глазах так же, как и во всем лице, было что-то необычное и т. д.

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

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