While searching for the solution of the same problem i decided to take different approach.
My query string was packed with lots of variables and since I was not able to access query string data from the web service, and I also did not want to send each query string variable as a separate parameter, I prepared my web method to expect one aditional string parameter.
That parameter was window.location (entire url of the page) in my javascript function on .aspx page
Once I had url in my web service, the rest was quite stright forward
Uri myRef = new Uri(stringMyWindowLocationParameter);
System.Collections.Specialized.NameValueCollection mojQuery = HttpUtility.ParseQueryString(myRef.Query);
Now my query string is contained inside myRef object and this is how I call it
// Instead trying to request query string like this
string myId = HttpContext.Current.Request.QueryString["id"];
// ... I called it like this
string myId = myRef["id"];
Maybe it's not the most elegant way but it solved my problem.