You Don't Say If The Car I Still Under Warranty Or Not
I am assuming that it is not or they would have just replace the switch, by now.
If so, the dealer has just a few tries at fixing this problem before having a "lemon law" possibly kick in.
Anyhow, has the dealer researched any Saturn TSBs (Technical Service Bulletins) that give them possible solutions to this problem?
I found two.
The first advises to replace the ignition switch, as the dealer claimed. An inconsistent contact inside the ignition switch between the printed circuit board and the contact finger can cause this, according to the TSB.
The other TSB has a list of procedures for the dealer to follow after they verify that the ignition switch has been replaced and continues to have problems. This problem is caused by an "early igniton switch bounce" while starting the car. The BCM (Body Control Module) in the car interprets this electrical "bounce" as a failure in the PASSLOCK system and disables the starting system. The BCM may need to be replaced, too. (My note: They can be quite costly.)
Also, they should be able to retrieve DTCs (Diagnostic Trouble Codes) from the BCM that may help them with a proper diagnosis. Have they done this, already?
You asked some questions:
"Would a lock de-icer (the kind with a heated pick) work?"
I don't think it would.
"What about a remote starter?"
Again, I don't think so. Until the starting issue is solved, I wouldn't advise adding any more components into the system. This could make it harder to diagnose and fix.
"Is there some kind of relearn process for the passlock system that would teach it to recognize the key?"
Actually there are relearn procedures that the dealer follows after replacing the ignition switch or the BCM. I don't know if they tried reprogramming the BCM or not or if it would help. Check in your Owner's Manual, too, but I don't think it can fix this.
My unofficial answer (opinion) is to be sure the dealer is aware of the TSBs. I'm pretty sure they have been, though. Also, these may or may not apply specifically to your car, but they can check by make, model, year, and the car's VIN (Vehicle Identification Number).
I think you are going to have to have it properly fixed, starting with the switch, first. The heat, sprays, remote starters, new keys and such aren't going to do it.
Depending on miles, you may be able to plead your case with GM or GM rep for help with the cost. This looks like an issue they have contributed to. Sometimes there are secret warranties or "good will". If this car is out of warranty, they have no obligation to pay anything and this is where "you can catch more flies with honey than with vinegar," and I would be as polite and considerate as possible.
What is the warranty? Please respond and tell us if the car is covered by warranty and please tell us the mileage and car's age or date of birth (delivery date).
P.S. GM has had issues like this for several years, first with the PASSKEY security system, and now with the PASSLOCK security system. Trying to keep insurance costs low for the customer, the cars have been made too secure! I hope you enjoy and continue to enjoy your car other than this temporary inconvenience.