(I haven't read the entire thread, and I don't intend to)
In response to the OP: It could easily have been DNS related. Even though you were connecting through the proxy, there's a good chance the DNS request (asking for the IP of gmail.com) was passed to the local/default DNS server - which instead of replyng with gmail's actual IP, replied with the IP of the "you have been blocked" page (or did something else not so nice).
Out of curiosity, what happens if you try something like:
http://1245019805/proxy.pl?url=http:.../&proxy=random
By using numbers (instead of hostnames), I'd imagine it circumvents some filters. The basic formula is:
(first octet * 16777216) + (second octet * 65536) + (third octet * 256) + (fourth octet)
So
www.samair.ru (66.246.218.29) for example:
(66 * 16777216) + (246 * 65536) + (218 * 256) + 29 = 1123473949
So while
http://www.samair.ru/proxy/ may be blocked,
http://1123473949/proxy/ might not be.