Не знаю насчёт кодирования, но первое что пришло в голову, это просто переходить по ссылке и забирать Location у редиректа:
Cache-Control:no-cache
Connection:Close
Location:http://www.onlinetrade.ru/item125724.html?from=ymarket&utm_source=yamarket&utm_medium=cpc&_openstat=bWFya2V0LnlhbmRleC5ydTvQmNC90YLQtdGA0L3QtdGCLdC_0LvQsNC90YjQtdGCIFJJVE1JWCBSTUQtMTAyNyBBbGx3aW5uZXIgQTMxICgxIEdIeikvMkdiLzhHYi8xMC4xIiBURlQgSVBTL0FuZHJvaWQgNC4xL1dpLUZpL0JsYWNrO2djanpkd1V2TEVTTmRoS1NDdkpta1E7
Для этой ссылки вес запроса вышел 389 байт, мне кажется, это не большие накладные расходы.
Чем такой вариант не устраивает?