Cruise... a LOT. I found ALL of them and believe me, after doing all the races, finding garages and houses and all that lot, LAST thing I wanted to do was cruise for bloody roads.... BUT there is way to do it. Step by steeep, one after another, calmly and I tenaciously driving. It helps having a fast car but not too fast - Corvette ZO6 is a great handler and has its top speed all right :)
Anyway, I did them by looking what I needed to drive through first and pallning my route across one square of map to another covering all roads I could find along the way. City centre is a proper pain in arse but its doable. Then in country side, drive to a junction, TURN and drive till next one then TURN again. After you have reached next bit of road you know already, you will have to go back to the first one and carry on doing this. If you have like 95%+ it gets real tricky, its usually all the simple anal stuff like motorway exits that HAVE to be driven thorugh. When you approach one of your last bits of road, game should recognize your efforts and reward you with 100% uncovering all those TINY bits you had missing but only with 99,9% :)