Pareto efficiency and inefficiency, as Michael Greinecker comments, are properties of allocations of resources. An allocation is efficient if there is no alternative allocation which makes someone better off without making someone else worse off. It is inefficient if there is an alternative which makes someone better off and no one worse off. The question ‘Are all externalities inefficient’ must be understood therefore as shorthand for something like the following: Are market outcomes always inefficient when externalities are present? The answer, as I shall show below, is that this is not necessarily the case.
For the avoidance of doubt, and to avoid over-complexity, I will focus on the case of negative production externalities, and assume a context in which the government enforces property rights and contracts, but takes no specific measures such as regulation or taxes to mitigate externalities. In particular, I assume that those who suffer harm or loss of utility as a result of externalities are not protected by specific property rights (such as right to a quiet environment where the issue is a noise externality). As a consequence, producers who are the source of externalities are not constrained by any such specific property rights on the part of others, so will mitigate their externalities only if they have a financial incentive to do so. In the absence of any such incentives, the market outcome will therefore be that the externality is unmitigated.
Here are some circumstances in which the market outcome would not be inefficient:
1. Where there is a continuum of options to mitigate the externality to different degrees and Coasian bargaining can reach agreement on an optimal level of mitigation
Coasian bargaining normally requires that there be just two or at most a very small number of parties involved, otherwise inter-party negotiation is likely to become too complicated and costly. What your question overlooks is that, often, negotiation need not be restricted to a choice between extremes (noise or no noise, payment or no payment) but can focus on trying to agree levels or degrees of mitigation (level of noise, level of payment). In the case of noise, for example, the factory owner may have options of fitting equipment that will reduce the level of noise but not eliminate it altogether. Such options will have costs, but probably less than that of stopping the noise altogether. Often (though not always) the marginal abatement cost, the cost of reducing the level of the externality by one unit at the margin, is an increasing function of the amount of reduction. Similarly, the marginal benefit to the neighbour of a reduction in noise may be greatest for the first unit of reduction and then gradually decline, the final reduction from barely audible to nil yielding very little extra benefit. Where this is the case, there may exist an optimal or efficient level of abatement where marginal abatement cost equals marginal benefit, as in the diagram below. Coasian bargaining among a small number of rational utility-maximising parties can (at least sometimes) result in a market outcome at that efficient level. Notice in particular that an optimum exists despite the fact that (as in your changed example) the cost of reducing the noise to zero, represented by the total area under the marginal abatement cost curve, greatly exceeds the total benefit from reducing the noise to zero, represented by the total area under the marginal benefit curve.
2. Where no available option to mitigate the externality represents a Pareto improvement on zero mitigation
Even if there are a continuum of mitigation options as above, it could be that marginal abatement cost exceeds marginal benefit at every mitigation level, as shown below.
If so, no level of mitigation represents a Pareto improvement on zero mitigation, which is therefore both the market outcome and the efficient outcome. Notice that in this situation there is no need for Coasian bargaining to reach the efficient outcome, so it does not matter whether the number of parties affected by the externality is small or large. This seems quite a plausible scenario: an example might be the construction of a small business premises marginally impairing the views of neighbours.
3. Where another form of market failure is present as well as the externality, and their respective effects exactly offset each other
Suppose for example that a good subject to a negative externality in production is produced and sold by a monopolist. Suppose further that there is no way of mitigating the externality while maintaining output, so that the only way of mitigating it is to reduce output. Because of the externality, marginal social cost will exceed marginal private cost to the producer. However, well-known theory shows that a profit-maximising monopolist will charge a price exceeding marginal private cost and restrict output. Whilst unlikely, it could in principle happen that these effects exactly offset each other so that the price charged equals the marginal social cost at the resulting output level, which will be an efficient outcome (in the absence of other complications such as consumption externalities).