Здравствуйте, odi, Вы писали:
odi>1. Продолжать поиски работы дальше. Но работодателей уже начинает волновать, почему я ищу работу так долго.
Можешь ответить, что везде предлагали "серую" зарплату, а ты хочешь платить все налоги, потому что честный гражданин

А с чего они решили, что ты долго ищешь работу? Со старой ушел до устройства на новую?
odi>2. Принять предложение с "серой зарплатой" и без трудовой книжки. Как мне просчитать последствия принятия такого решения? Ясно, что там придется работать не менее полугода-года-полутора лет, так как если работать меньше, то опять возникнут вопросы про "почему ушли ?" или "если там так плохо, то зачем же устраивались ?"... А это значит, что еще 1-1,5 года без трудовой книжки.
Без трудовой книжки — это черная зарплата, действительно не стоит. Серая — это когда официально работаешь на зарплату в 2000 руб., а остальное получаешь в конверте и т.д. Так что если нужная только трудовая книжка (думаю, пригодится), то можно и на серую.
Я в свое время не заморачивался по этому поводу. Если бы сейчас предложили что-то хорошее на серой зарплате, то навряд ли бы отказался только из-за "серости". Хотя надо рассматривать варианты. В некоторых случаях "белая" более выгодная из-за налоговых скидок и т.д.
odi>Учитывайте в своих ответах, я выпускник, совсем недавно столкнулся с поиском работы, опыта поиска работы у меня мало. Наверняка, кто-то уже оказывался в моей ситуации, как вы разруливали проблему 
ХЗ. Мне отказали "по-настоящему", то есть когда я серьезно рассчитывал получить работу, а не дали, только один раз. Но я выбирал компании не по серости или белости, а чем буду там заниматься, какие отзывы, общее впечатление и т.д.
Возможно проблема в том, что "белые" компании, как бы сказать, большие и крутые типа Яндекса, Сана и т.д., и там очень придирчиво относятся к кандидатам, а студент с общим стажем в C# менее года смотрится не очень солидно.
Если ответили отказом, то не стесняйся вежливо уточнить, что компанию не устроило. Не факт, что скажут настоящую причину, но ответ все равно будет полезен, ИМХО.