Помогите вычислить кракозябры

На сайте есть поле ввода, инфа(название города) в которое может быть заранее подставлена по ссылке через $_GET. Как стало ясно, а может я и ошибаюсь - роботы отсканили сайт и в выдаче надовали "кривых" ссылок с этим $_GET ... Сейчас в базу частенько попадают такие города как:

Исходное / расшифровка / должно быть

----------------------------------------------------

Алматы - �лма�‚�‹ - Алматы

Шð°Ñ…Ñ‚Ñ‹ - Ш���…�‚�‹ - хз

Армеð½Ð¸ñ Г.ðµñ€Ðµð²Ð°Ð½ - ��€ме��и� �“.���€е��ан - че-то там.Дагестан

Макðµðµð²Ðºð° - �œак������к�� - ...

Андð¸ð¶Ð°Ð½ - �нд����ан - ...

Расшифровывал автоматикой на http://www.artlebedev.ru/tools/decoder/ дало как ISO-8859-1 > UTF-8 но как понятно - это очень приблизительно

Что так ломает названия и как это побороть? То что виноваты кривые ссылки, а не пользователь - есть возможность указать имя - так оно нормально сохраняется, в то время как город криво ((