I have come across this many times in my shop. It's cause is a bit complex so I'll just tell you the work around. You have to get rid of these Deleted Global Colours in your file. Do this by creating a new document same size as the corrupt document. You have to copy and paste your art into the new file but NOT by just copying and pasting. You instead have to select all the artwork from the offending file and drag into your new document. This will bring in all the deleted global colours but you can then choose delete unused colours from the swatch menu fly-out. I have an action that does this with one keystroke so it can be pretty quick if you have a lot of files like this.
Just deleting them in the original file is not good enough, they will come back. Leaving them in your file causes severe slow downs and frequent crashes. It took me a while to figure this all out but trust me it works.
Good luck mate,
All you have to do is record your keystrokes in the actions pallett and save them. If you want I can email you the action that I use to delete unwanted colours but I would need your email address for that.