I don't think either the CPC or LPC were ever left totally without representation in Quebec, and neither party ran a successful campaign in the rest of Canada largely based on portraying Quebecois as bogeymen.
Though not necessarily disputing your larger point, the situation in Quebec in the 1990s were close. Recall that the Bloc Quebecois was formed by a good chunk of the Quebec nationalists Mulroney allied with to form a national coalition; for two elections the PCs had no representation there.
No campaign proper has attacked the Quebecois as bogeyman (mostly because Harper still thought gaining ground in Quebec was a necessary step to a majority up to 2011), but think about the campaign against the "separatists" that dominated their messaging from 2008-9. Since Harper did cobble a majority excluding Quebec in 2011, that weapon is back in their arsenal.