Republicans easily win Virginia in off years. Just ask Gov. Cuccinelli and Sen. Gillespie.
Bolling could have beat McAuliffe, Cooch is just too conservative to run statewide (in 2009 he won with McDonnell's coattails, and NOVA has grown since). Gillespie was practically ignored and everyone was shocked to see him overperform polling. People expected Warner to win in a landslide like in 2008, but if the NRSC knew Gillespie was secretly campaigning strong, they could have helped give him the final push.