The reason I'm posting this is because I think the solution we found could be useful for others.. So here's the story.
Some time ago we were trying using Google App Engine to create some king of a web-crawler. And pretty soon we have found that doing HTTP requests to other sites with GAE is not a piece of cake. It's more like a piece of something less tasty...
