Как, где узнать снята ли судимость?

Зачем узнавать! Это долго и малоперспективно! Есть все основания предполагать. что судимость за Вами в ИЦ МВД так и тащится. Я бы на вашем месте поступил бы так ( а вы уж сами решайте) .
Во-первых, обратился в суд, который выносил приговор в порядке ст. 400 УПК с ходатайством о снятии судимости, в связи с тем. что приговор был отменён надзорной инстанцией и по тем мотивам. которые вы пишете в вопросе. Вторым требованием поставил бы вопрос об исключении сведений о Вашей судимости из ИЦ МВД, в связи с оправданием ( пусть суд разбирается это не Ваше дело). .
В ходатайстве надо просить суд также истребовать сведения о Вашей судимости из ИЦ МВД, так как Вам этих сведений без помощи суда не получить. Суд ВЫНУЖД ЕН будет запросить спецпроверку. Тогда ( при ознакомлении с делом) Вам будет ясно значитесь ли вы среди ранее судимых или нет.
В этом вопросе, если по ходу будет меняться обстановка, НИ В КОЕМ СЛУЧАЕ не соглашайтесь на любые предложение суда отозвать своё ходатайство о снятии судимости. Помните, что Вам нужно только письменное судебное решение по вопросу снятии судимости, а не слова : " всё нормально, что вы волнуетесь, всё давно прошло" и прочее... .

При каждом городском (областном) УВД существует Информационный центр.
Со своим запросом Вам нужно обратиться в приёмную начальника УВД

Судимость погашается:
а) в отношении лиц, условно осужденных, - по истечении испытательного срока;
б) в отношении лиц, осужденных к более мягким видам наказаний, чем лишение свободы, - по истечении одного года после отбытия или исполнения наказания;
в) в отношении лиц, осужденных к лишению свободы за преступления небольшой или средней тяжести, - по истечении трех лет после отбытия наказания;
г) в отношении лиц, осужденных к лишению свободы за тяжкие преступления, - по истечении шести лет после отбытия наказания;
д) в отношении лиц, осужденных за особо тяжкие преступления, - по истечении восьми лет после отбытия наказания.
Категории преступлений по тяжести см. ст. 15 УК РФ.
Удачи

Поинтересуйтесь в милиции... а вообще удачи вам во всем=)

обратитесь в УИН или в милицию