Is that a routing issue, or a fragmentation problem? Reducing your MTU on a GRE link greatly improves performance.

I'd be interested in hearing if there were any ISPs that didn't just forward GRE packets using normal IP routing conventions.

Absolutely no idea. AFAIK they just disappear into a void.

Used to be like this on Demon, Virgin Media and Easynet. The latter fixed their stuff circa 2007 however.