В официальных документах предпочтительна форма мужского рода, то есть следует выбрать первый вариант.
Верно: Иванов И. И., заведующий поликлиникой.
Правильно: заведующие структурными подразделениями.
Правила не изменились. Изменились, по-видимому, лишь бюрократические требования.
Корректно: заведующая кафедрой Иванова; был назначен (прибыл) А. А. Иванов.
Корректно: с заведующим (чем?) лабораторией.
Мужской род уместен в строгой деловой речи, где важно сообщить о должности безотносительно к полу (например, в приказе: назначить заведующим детским отделением Александрову...). В обиходной письменной и тем более устной речи верно: заведующая детским отделением.
См. вопрос 295779.
Правильно: заведующий лабораторией. Такие слова, как заведующий, управляющий, командующий (т. е. существительные, произошедшие из причастий), управляют творительным падежом.
Всё верно: заведующий кафедрой (такой-то) экономического факультета.