Take very long. When I ran PROFILE, I noticed that all label lookups were doing AllNodesScan instead of NodeByLabelScan. I don't recall deleting any special indexes for node labels, but if I did, is there a way to recreate them to get fast NodeByLabelScan lookups again?
An update on this. I have tried creating a few nodes of a new label :TestLabel, and finding nodes of that label does not use the NodeByLabelScan for search. So it appears somehow the functionality is broken for the DBMS. Restarting has not fixed it.