Могут ли уволить работника, если обнаружилось, что он когда-то (лет 20 назад) находился под следствием?

Чтобы вам было совсем понятно, имейте в виду, в частности, следующие законные основания увольнения. Согласно ст. 83 Трудового кодекса РФ (далее - ТК РФ) , трудовой договор может быть прекращен с работником (т. е. увольнение) , в частности, В СЛУЧАЕ ОСУЖДЕНИЯ РАБОТНИКА К НАКАЗАНИЮ, исключающему продолжение прежней работы, в соответствии с приговором суда, вступившим в законную силу.
А согласно ст. 84 ТК РФ, трудовой договор прекращается В СЛУЧАЕ, ЕСЛИ трудовой договор был заключен в нарушение приговора суда о лишении конкретного лица права занимать определенные должности или заниматься определенной деятельностью (как правило в таких случаях указывается период в течение которого данное лицо не вправе определенную должность) .

Не могут. Виновным в совершении преступления гражданин может быть признан только по вступившему в законную силу приговору суда

ничего не будет. В ТК РФ нет такой статьи увольнение из-за наличия судимости.

По новому закону (точно не помню №) В учебные заведения не могут брать отсидевших, и поэтому трудоустраивающиеся учителя должны предоставлять справку из УВД об отсутствии судимости а на библиотеки такое не распространяется

по закону - ничего

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