Question: We are a small team of developers making and maintaining a software product with a high number of users. 

We are also in direct contact with users who ask us many requests about the product. 

We don't have access to business information (what kind of deal a specific user has with the company that employs us). 

We don't have enough resources to address all the user requests, and will have to refuse some of them. We treat in priority the requests that seem easier to comply with ; or that could benefit most users. 

How can we gracefully notify those users who made requests that we will not be able to process?  

How to tell them that what they asked for is not possible ; while avoiding frustrating them?

Answer: 
Pass information up, and receive decisions that come down.

You should record all the client requests in an issue tracking system, but place them into the backlog (so they aren't worked on). The project manager (you should have one, of some sort, I hope) will review the requests on a regular basis, and decide which ones should be worked on. That PM is the person who should have the business and contractual knowledge (from the client) and techncial knowledge (from the request) in order to prioritize the work. 

Once you have that type of workflow in place, you never have to say no to a client - you always say that you'll ticket it, and Ms XYZ will prioritize it.
Get together with your sales people/whoever manages the business side of the contracts for which you do the development. You have information they need, and they have information you need.

You need to know what you *should* do for the clients. The sales folks need to know what you *could* do for the clients, and how hard (read: expensive in salary hours) it would be.

You don't want to sever all contact with the customers. It's good if developers have a clear idea of what the customers actually want to do with the software. But you do need to get the sales people involved more. Handling your problem, is part of their job.