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: 
The golden rule: The customer is always right - if the customer pays for it. If your manager comes to you and tells you that the customer is paying for a feature or a change, and tells you to do the work, then you do it. Otherwise you don’t. 

Find out who in the company can make a decision whether work will be done at all, and for what price. Then when you get a request, you say politely “I’m sorry, but this is something I cannot decide. Please contact so-and-so about it”.

PS Just because the customer is willing to pay doesn’t mean they get it. Someone quite high up needs to decide about the company’s strategy. Any request costs money, not just for the work done, but also for all the other work you *should* do instead.
I agree with all the other answers on that you need the contract info to make these decisions and pass the negotiation of features onto whoever is handling those. That needs to go to them.

However, I want to add a warning. Be careful just handing off the decision on whether something gets added to the salespeople/management. A feature might be impossible, it might be a security problem, or it might require that so many variants of the software be created that maintenance becomes exponentially more difficult. 

Management might easily agree that a button should be moved a couple pixels over. That couple of pixels may seem trivial for them, but could require adding the ability to add a custom style sheet for each client. Moving from a one to one relationship for items to a one to many relationship is something that many non-technicals see as 5 minutes of work. It isn't. 

Highly complex requests are going to have to be refused anyway, but it will be a lot less graceful if sales agrees and then development tells them it cannot be done.

Try to get sales to check with the development team before they approve a new feature in an agreement.