SPF and DKIM are different things. It’s difficult to troubleshoot without being able to check the actual records, which means knowing the domain too. DKIM records are completely public (at least, they can be seen by anyone who receives an email from the domain in question).
The DNS records for that selector are in place and seem to be ok.
What is your email host actually saying is the problem?
If you send yourself an email and look at the headers, you will find a DKIM-Signature line. Can you share what the value of the s parameter? It should be the selector value.
And for reference, dig output showing both your record and mine, for comparison. The dig links are based on live queries, if you make changes in Cloudflare’s dashboard you should see the changes if you refresh after about a minute.
@lmengerink Any chance that maybe you used the new name, but the old key? Otherwise nothing looks off at the moment. It is possible that some tool is caching an old/missing record and returning a false error too.
You should not really just change the active DKIM key when in use. There is a good process documented by the M3AAWG, but some major providers use two selectors and flip from one to the other when they need to rotate.
Do you send all email via a different provider to your incoming email? The format of the DKIM you posted looks like that from Red Tail Technology, but if you are sending through Smarsh.com (as in your SPF) their keys look very different.
Who is signing the email, and how did they give you the signing keys?
Can you share a DKIM-Signature header from a malfunctioning email?
This appears to be the issue. While the email provider assured me that DKIM would work through Smarsh, it appears to be a limitation within Smarsh itself.