So far no problems for me at the 135 mm end.
If low light or nite shots will be on my tripods of course. I've tried 800-1600 ISO without tripods and some shots will be ok as well. Tripod shots are dependent on the tripod u use of cos.... mine's a manfrotto and seems to work well.
The difference I think is not whether there's VR with the 135mm but rather whether you need the reach from 135mm to 200mm. If you require to shoot at 200mm, frankly, VR is a must.
Bottomline for me is that if I am travelling and doing some leisure photography of buildings and landscape, I don't really need to have anything longer than 135mm. In fact, was thinking of getting the 18-105mm VR some weeks back (BBB virus) but successfully resisted it cos the 18-135mm is working fine for me. Come to think of it, I use my Tokina 11-16 f/2.8 a good deal when I travel, esp for landscape shots. I went Phuket on vacation for almost a week last month and had nothing but the 18-135mm with CPL on my cam. I didnt miss any of my other lenses.
That said, my impression of the 18-200mm VR is that it is very versatile, and takes away the hassle of changing lens. If you need that, then buy away ! ;p