With gun shops, expect to pay a lot. I've only seen one used SA58 for sale at a gun shop. The asking price was $2,000. I talked to the owner, and he admitted it was his personal rifle, and he didn't really want or expect to sell it. He had it up there just in case someone really desperately wanted one (or didn't know better) and was willing to pay a ridiculously high price. He also needed to take up some wall space. If he sold it, he was just going to buy another one.
I paid $1400 for my SA58 Para Congo about a year or so ago. I bought it from a THR member who advertised it in the classifieds section. It has the 16" barrel with short Belgian flash hider, folding stock, rail front handguard, extreme duty scope mount, etc. It's a beauty, and I feel like I got a very good deal.
My suggestion is to watch the classifieds here and on FALfiles, and auction sites like Gunbroker.