Found the cause and the solution with the help of Joshua on support
The SAML logout request was generated by a library we are using, saml2-js. It seems this library had an outstanding pull request to fix the SAML logout request to add in the nameid_format attribute to the nameid element in the logout request. Setting this attribute solved the problem, as per Joshua's suggestion:
Ideally, when completing a logout request, FusionAuth is provided a Name Id format of:
urn:oasis:names:tc:SAML:1.1:nameid-format:emailAddress
or
urn:oasis:names:tc:SAML:2.0:nameid-format:persistent