Thanks for trying, I've created a minimal script to reproduce the issue. In creating the script, i've found two extra requirements:
a unique constraint on serviceid
version 4.3.1 (i can't reproduce on 4.4.6)
Looking at the change history i can see it was fixed in 4.3.6:
"Fixes a bug in node index seek on a unique property in write queries. For example MATCH (n:Node) WHERE n.unique IN ['does not exist', 'exists'] DELETE DETACH n would fail to delete nodes if there is a unique constraint on unique and at least one predicate does not match any nodes."
CREATE CONSTRAINT service_serviceid ON (s:service) ASSERT s.serviceid IS UNIQUE;
CREATE (n:note {note: 'Note 1'});
CREATE (n:service {serviceid: 'b'});
MATCH (n:note), (s:service)
CREATE (s)-[r:servicenote]->(n);
MATCH (n:note)<--(s:service)
WHERE s.serviceid in ['a', 'b']
DETACH DELETE n;