spf=fail

spf=fail is the strongest negative SPF result. The receiving server checked the domain in the envelope sender (smtp.mailfrom), found an SPF record, and that record said outright that the connecting IP address is not allowed to send for the domain. Usually that is because the IP matched nothing and the record ends in -all.

What the RFC says

RFC 7208 §2.6.4 calls fail an explicit statement that the client is not authorized to use the domain. It comes from a mechanism with the - qualifier matching (§4.6.2), and in practice that mechanism is almost always the final -all. §8.4 leaves what happens next to the receiver: it may reject during the SMTP conversation (with a 550 reply and enhanced status code 5.7.1), or accept the message and record the result in a header, which is why you are reading this one.

Received-SPF: Fail (mx.example.org: domain of billing@example.com does not
       designate 203.0.113.45 as permitted sender) client-ip=203.0.113.45;
Authentication-Results: mx.example.org;
       spf=fail smtp.mailfrom=example.com;
       dkim=pass header.d=example.com;
       dmarc=pass header.from=example.com

Why it happens, most common first

1. Forwarding. You set an old address or a university account to forward to this mailbox. The forwarder delivers from its own IP but keeps the original bounce address, so the original domain's record does not list it (RFC 7208 §10.3, RFC 7960 §2.2). The snippet above looks like this: SPF failed, but a DKIM signature survived and DMARC still passed.
2. A sending service nobody added. A new CRM, help desk, invoicing tool or website contact form sends as the domain, and its include: never made it into the record.
3. A record edit went wrong: an include dropped, an IP renumbered, or a migration to a new mail host half-finished.
4. Forgery. Someone sent mail using the domain in the envelope from a server they control.

If you received this message

Look at the rest of the line. If DKIM passed for the From domain and DMARC passed, the SPF failure is almost certainly forwarding and the message is fine. If DMARC also failed and the From domain is the one SPF rejected, treat the message as forged unless you can see a forwarding hop in the Received chain. Paste the full headers into the analyser to see both side by side.

If you own the domain

Find the sending IP (it is in client-ip= or the newest Received header), work out which service owns it, and add that service's documented include: or an ip4:/ip6: entry. Keep the record within the limit of 10 DNS-querying terms (RFC 7208 §4.6.4), or the fix turns into a permerror. For forwarded mail you cannot fix SPF. Make sure every stream carries a DKIM signature with your domain, because that is what survives forwarding.