Т.к. постоянно приходится работать с архивами, постараюсь подсказать. Сохнут - еще "та кантора Никанора". Попытайтесь найти следующие документы по деду:
1. Свидетельства о браке (иногда писали национальности брачующихся);
2. Военный билет (пресловутая 5 графа);
3. Копии формы А (карточка о прописке из ЖЭКа) либо домовую книгу, где записаны были дед и бабка (писалась однозначно национальность);
4. Трудовую книжку (иногда писали);
5. Характеристики (писали ВСЕГДА);
7. Различные формы с мест работы по деду из отдела кадров (писали национальность ВСЕГДА);
8. Если был судим или просто привлекался к ответственности, то постановления, решения или приговоры судов; (писали национальность ВСЕГДА)
9. Нотариально заверенные копии документов (старые копии этих документов);
10. Комсомольский или партийный билет (писали национальность ВСЕГДА);
И еще. Нужно начинать искать не с госархивов, а с архивов отделов РАГС (ЗАГС) района, города, области. И только потом переходить к поиску в госархивах. Почему так? Писать долго.