This is an icky little problem that I’ve seen with just about every single iteration of Windows out there. The solution is pretty simple:

1. Open the control panel.
2. Click on the System and Maintenance icon.
3. Select Administrative Tools.
4. Open Services.
5. In the list of services look for the one called “Print Spooler.”
6. Restart the print spooler.
7. All of the deleted or cancelled jobs should vanish and print jobs left in the cue should begin to print.