There are several aspects to be considered in suggesting an answer to your question. These include:
- Getting better control of the resources;
- Improving the estimates to recognise the reality of your situation, where task duration and task effort are potentially quite different;
- The relationship that your company has with its customers (at all levels);
- Your authority to make things happen.
Getting better control would require that you can agree with the line manager some form of guaranteed level of resource availability. Even if this is significantly lower than 100%, you would have some comfort that you would have at least a minimum level of resource availability. If such an agreement can be reached between you and the line manager, you may wish to consider publicising the agreement to senior management and explaining the benefits of this to them, to encourage them to honour the agreement.
Improving the estimates may require that your resources provide you with an estimate of the effort required, while you apply a scaling factor to convert this to a duration. For example, if you anticipate that your resources would only be available 70% of the time, and they have suggested that they can do the work with 7 days of effort, you should estimate 10 elapsed days for the work. This may seem too simplistic, but it may help. Your estimates will potentially improve over time as you build a better set of metrics, which may vary from person to person or skill to skill.
The relationship between your company and its customers is key to this. If you are having to justify slippage, and your customers are complaining when you fail to meet deadlines, is there an opportunity to escalate these complaints to your own management? Do your managers have to deal with the customer complaints, and if so, do they then take steps to resolve the causes of the complaints? If they don't meet with the customers sufficiently often, then perhaps they need to be invited to customer meetings - but don't just drop them from a great height. Brief them in advance so that they can support you and hopefully help you to work through some of the issues.
Finally, as a project manager, you need to have sufficient authority to make things happen. If this isn't the case, you may have to have a heart-to-heart discussion with your own line manager, and see what can be done to give you the necessary authority. Bear in mind that one part of the PM's role is risk management, and it seems to me that you may not be carrying this out effectively - if at all. Anything that is a risk to the success of the project should be flagged as a risk and managed accordingly, and escalated as necessary.
It should be possible to make a significant improvement in a positive way, without breaking any existing good relationships. You don't need to become an ogre to make things happen, but you do need a level of management support. If this is not forthcoming, then you have a different problem...!