Grand AM 99 problem

I have an unsual problem with a 99 Pontiac Grand AM. Sometimes when I try to remove the key, it stays in and will not come out. I took it back to dealer and spent $300 to replace some type of solenoid, but that did not fix it. I took it back to repair shop and they said they cleaned it and everything should work fine. That didn't do it either. Any ideas?