WITH n.name AS name, all(x IN nodes(path) WHERE x.salary >= 19999 AND x.address = "Paris") AS check
WITH name, collect(check) AS checks
WHERE all(x IN checks WHERE x = true)
RETURN DISTINCT name
ORDER BY name
It looks like you're not really concerned about paths, just that all friends in a 3-depth radius adhere to the conditions.
In that case, we can collect all of their distinct friends in that radius, then apply the all() predicate function:
WHERE n.salary >= 19999 and n.address="Paris"
WITH n, collect(DISTINCT b) as friends
WHERE all(friend IN friends WHERE friend.salary >= 19999 and friend.address="Paris")
RETURN n.name as name
ORDER BY name
I'm using a subquery to constrain the scope of the collect() aggregation, otherwise it may stress the heap depending on the number of nodes in your graph.
If the WHERE all() in the subquery fails, then that row will be dropped and won't continue in the query.
Your :friend*..3 variable-length relationship is directed. Was that intentional? If a single :friend relationship indicates it is reciprocal, and not one-way, then you might want to drop the direction in that MATCH pattern so it can traverse a :friend relationship in either direction.
You really should be using labels here, otherwise this is an AllNodesScan. Also, you should consider an index, at the least on the label and address, but you would get better time if it was a composite index on address and salary.