First of all.. If your rubberseal are shot anyway - cut the windshields out! Run a blade just thru the seal under the aluminum trims, leaning towards the glass. Run the blade 3-4 times, and you should be kind of feeling progress..
Cut from outside!

The front windshield is easy to crack if presure is is "un-equal" - let's say on one corner - but by cutting the seal, there is (or should!) be absolutely no problem.
The rear windshield is really hard glass, and you can throw it arround without it's going to crack!
The autoglass places you have been to, probably lack the knowledge, due to todays very thin glass and glued-in technic.

I hope you get my english!

When re-installing new rubberseal - always tighten up with filler (don't know the english word/brand - but NOT silicon-based, but the like..)

Before anything! - BEWARE when removing those aluminum trims! - just a tiny bend, and they are shot! Here YOU should do the job.. Take good care and don't rush!

--
/Soren