The good news is that you have a power supply that can easily run any single GPU out there.
What resolution are you trying to run the game at? If it's 1080p I'd recommend a Radeon HD 7850 or 7870. Either one will run the game on ultra quite well, provided your CPU doesn't hold you back. If you go for the 7850 be sure to get the 2GB version if you want to run the game with high resolution textures.
If you are looking to spend less money, the Radeon HD 7770 would also be a decent upgrade. It doesn't have enough muscle to do ultra in Skyrim at 1080p, but it will pull off high settings and can handle ultra at lower resolutions.
That's strange... The 7000 series cards are the current series, they are still in production, no way they have been discontinued. Which retailer are you looking at? It could be they don't have any in stock right now for whatever reason.
It is a decent model. You probably won't do better unless you want to spend more for the really high end coolers and/or factory overclocked cards. There are some slightly cheaper 2GB models, but they tend to be from some of the not so great brands.