You think Kinkos in the US is a struggle, you should try Kinkos in Australia!!! I've never heard of anyone plugging directly into their network here in Oz, and most of the Kinkos stores are not open 24/7! When I do use them, I always save as a PDF. I haven't had the problems you list though. When I was on OS9, I used the shareware Print-to-PDF chooser extension (making sure the PDF had a minimum resolution of 300DPI), but now with OS10.2 I use the built-in PDF generation. It is a little jaggy when viewed on the screen, but it seems to print OK. Nothing beats native printing though, and luckily Sydney has a great plotting service company with full VW - the local VW distributor is in the same building. Practically all my plots are A2 up to A0 so touring a large format printer is not possible for me.
If you are going to the UK, I think you'll find Andy Voller is a subscriber to this bulletin board, and he is based in London working for VariLite. Try sending him a personal message.