Тоже читал про это не раз.
В тоже время моих выселяли из Украины, однако два года назад деда по моему заявлению реабилитировали в Алтайском крае. Интересно, от чего это зависит?

Реабилитацию за нахождение в трудовой армии в Челябинске тоже можно получить в РФ, даже если выселение было из Украины. Знаю такой случай.

Полагаю, что это зависит от того, как реабилитирующий орган оценивает место принятия решения о применении репрессии. Если речь о выселении, то это будет Украина, если о нахождении на спецпоселении (а архивные дела стали заводить лишь в 1949 году по месту поселения и после выхода в ноябре 1948 приказа о выселении навечно ), то это будет РСФСР. Так что если б вы просили реабилитировать только за выселение, то отправили бы в Украину, а поскольку на территории РФ тоже была применена репрессия, то и реабилитировали в РФ. Ещё это зависит от возраста вашего деда на момент выселения. Если его выселили из Украины ребенком в составе семьи, то формально репрессия к нему не применялась в УССР, а пострадал он от репрессий (спецпоселение) уже только в РСФСР, будь то персональная репрессия (взятие на спецучет после 16 лет) или проживание на спецпоселении вместе с репрессированным родителем.