Здравствуйте Тимур Мукажанов, Вы писали:

ТМ>Проблема такова — сидел я в UK (Великобритании) и работал, но на прошлой неделе получил я нотис (то, что эти господа мой контракт продлять больше не хотят) и решил поискать тут новую работу. Но как-то все рекрутеры тухнут когда слышат, что с нашим замечательным гражданством нужно разрешение на работу... Может кто подскажет как можно обойти или агенство, которое может сделать его на себя...

Work permits are given to a company, which employs you.
There is no way around.

You have to stress that making work permit takes far less efforts and time than many companies would think. When speaking to job agencies, suggest that they put your CV forward and that you will discuss the matter of work permit during an interview with potential employer.

Hope it helps,
Sorry for writing in English — don't have Russian keyboard.