If the solenoid tests good, the right Ohms, and you can find out why the solenoid overheated in the first place and fix the problem, you can rescue the solenoid. Note, however, that there may have been damage done to the solenoid that would make it easier to fail if overheated again.
This won't work with metal sleeves. If I find an overheated solenoid with a metal sleeve I replace the solenoid and sleeve.
I take a small screwdriver and put it between the sleeve and solenoid casing. I then pry and break as much of the sleeve as possible, working from both ends. I then put a drum sander attachment on a Dremel tool. I slowly sand off the part of the sleeve that has been fused to the solenoid. You will need a bright light so you can see how much you are sanding off. Usually the sleeve and solenoid are different colors so you will know when you have sanded all of the old sleeve off. You don't want to sand the solenoid plastic. After all of the sleeve has been removed, sand the inside of the solenoid with a finer sandpaper to smooth the wall of the cylinder and then clean. Both solenoid and sleeve should be clean and dry. Try putting in a new sleeve. Use absolutely no WD-40 or oil to help get the sleeve in! If it hangs up, you will need to find where it hangs up so you can do more sanding. Don't force the sleeve in! You won't be able to remove it. Often the inside wall of the solenoid will bulge and require some sanding, but test putting the sleeve in often. You don't want to remove too much of the solenoid inner wall - there's wires under there!
This technique is good for saving original parts, for people who need to get a pin working ASAP and for those of us who are too cheap to spend the money on a new solenoid. For others, buying a new sleeve and solenoid is the best solution.