I have only been in this situation with internal tools where our stated goal was to best serve any whim of our "customers" in a situation where there was no way to predict needs in advance. So take my answer with a grain of salt.
My view is that the decision is often political, and unless you're the head of the company it might not even be up to you. The cost of unsatisfied customers going over your head to your boss can be more damaging.
I'm a big believer in agile and continuous requirement gathering that does involve seeing how users work with the product, and trying to match their needs. However, every user has his individual "nice to haves" and there's no way to satisfy everyone. If you have multiple target users, democracy is a good system - only implement things that the majority of the users can benefit from.
If your clients are a cohesive group (e.g., you're making it for users in a specific department in a specific organization), run a Wiki site or something like SO or other engines where they can list and then collaboratively vote on possible features. Make it clear that you will give priority (but no guarantees) about higher rated features, and that you're probably not going to give priority to things that don't get votes from others.
In doing so, you may be able to get the clients to apply some collaborative filtering (or peer pressure) on ideas. You will also get some visibility, so people can see why their wishes were not respected. An important side benefit is that whoever requested a feature now has an interest in formulating the request and its rationale well, so that they can get others to vote for them. This will eliminate some asinine half-baked ideas.
Of course, an underlying assumption of all this is that you budgeted some time to "misc features" with whoever is paying for the projec.