В начале 1951 г. Постолюк был лишен Золотой Звезды, но на каком основании, неизвестно, так как судим он тогда не был. Его сестра Валентина Павловна Филенко вспоминала, что на ее вопрос о причинах лишения брат ответил, что
Сестра Постолюка В.П. Филенко, уже после смерти брата, пыталась восстановить его в звании Героя. В середине августа 1988 г. обратилась с заявлением к бывшему председателю Президиума Верховного Совета СССР товарищу А.А. Громыко с просьбой сообщить ей причину лишения брата звания Героя и возможности его реабилитации и восстановления в звании.
На свое заявление из отдела наград Президиума Верховного Совета СССР она получила 16 сентября 1988 г. ответ: «…
В.П. Филенко обратилась в РОВД Полесского района, где она в то время проживала. Оттуда был сделан запрос в ИЦ МВД УССР по вопросу судимости ее брата 1950–1951 гг. 2 февраля 1988 г. ей пришел ответ, что МВД Украины данными о судимости А. Постолюка не располагает.
Валентина Павловна пишет письмо генералу армии Шкадову с просьбой о реабилитации и восстановлении в звании. Из Главного управления кадров МО СССР был сделан запрос по месту последнего проживания Постолюка
Таким образом, трижды судимый за хищение госимущества Постолюк А.П. провел за решеткой в общей сложности 2 года и 9 месяцев.
В отношении обстоятельств лишения Постолюка звания Героя Советского Союза в начале пятидесятых годов на телефонный запрос Главного управления кадров Министерства обороны от 15 мая 1989 г. Военная Коллегия Верховного Суда СССР ответила, что такими данными не располагает. Тем не менее в ГУКе не нашли достаточных оснований для возбуждения ходатайства о восстановлении А.И. Постолюка в звании Героя Советского Союза.
Днепр — река Героев. — Киев, 1983 г. — С.91.
Герой Советского Союза А. Постолюк. Как мы штурмовали высоту // Патриот Родины’ 1944 — май 21.