I think it's OK to charge a token fee (like $500) depending on your target audience and industry. It allows you to filter out clients who aren't serious buyers, and are just "shopping around".
The trick to charging the fee however is that you need to deliver some value. For example, we do business automation consulting, and the value we deliver when speccing out a project is a business process diagram that neatly outlines all the inputs, transformations and outputs of a given process. It tends to be an eye-opener for our clients and helps us demonstrate our worth up-front. From then on, the actual consulting work begins, followed by the engineering work (software implementation/customization).
Our solutions range from simple, commoditized stuff using enterprise tools (e.g. accounting department receives paper invoices, then staff keys them in manually into the accounting software - we convert that to a 95% automated system where invoices are scanned, values are OCR'ed off them and automatically pushed to the accounting system) to "fairly advanced" (e.g. custom APIs, specialized UIs, backend validations/triggers/approvals etc.) that involve a fair amount of programming.
We find most of our clients through referrals (either from existing clients, or from our partners), although we also do some cold-calling and telemarketing.
I'm just one perspective on this, there are others on the thread. But this stuff is all I've been doing since 2005 and I'd make a case that I've gotten reasonably good at it, so I'll go to bat for my perspective here and say that the advice to charge prospects for scoping work is bad, and you should avoid it.
It stopped happening entirely once we started charging a token fee. We realized that if we could convince clients to pay for a spec, even if it's a small amount, we have basically "soft-closed" them, which makes the rest of the engagement easier because money has already exchanged hands and trust has been built. Indeed, in our CRM system we move such clients to "existing customer" category, because that's what they are, and we treat them as such. (It also gives us the opportunity to name-drop them when needed, e.g. "we have done business with X").
It does occasionally give clients pause, especially if they are, like I said, just shopping around, and need convincing. But we don't care too much about such clients anyway.
If you get to a point where pre-sales work is grinding you down to the point where you need to do something about it, the right response is to raise your rates, so that the work that does close offsets the work you do on projects that don't. You should be constantly doing that anyways (it's hard! we're not awesome at it either, though we do try to do it once a year), so look at spec work as a forcing function.
That's another reason charging for nickel-and-dime rustproofing stuff like specs and proposals is bad business: it's way less valuable than actual delivery, and so charging for it makes it harder for you to set high rates.