So it’s hard to make general comments on this kind of thing because a) it depends on the shape of your data, and b) we’re constantly changing how things work behind the scenes to try to make things faster, but a few thoughts:
-When you have a list stored on an item, that list is loaded whenever that item is loaded. This is bad if it’s a really huge list, because it means fetching that item is slow. But, it means that if it’s a short list, retrieving items on the list is much faster, because they are already loaded. I think this is probably why @potentialthings saw a speed improvement. The general rule is if you expect things to scale to large numbers, it’s better to use a reference and do a search for, but if you know it’s going to be fairly limited, it’s faster to store it on a list.
-However, we are probably going to change this at some point: the current behavior of loading the entire list when you load an item is one of our current scaling limitations, since it means that there’s no way of making infinitely scalable many-to-many relationships. So, it’s on our list of things to change.
-When testing these kinds of things, it’s very important to have an isolated test page that just has the search on it. On a big page, if there’s a bunch of data all being loaded at once, sometimes the thing you’re looking at might actually be fast, but it’s getting queued behind slow stuff, so you’ll end up looking at the wrong culprit.
-When you first create a new search that you haven’t done in your app before, and you have a lot of data, it will run slow at first, then speed up after a while, because we have code that looks for big searches and automatically builds database indexes to optimize them. So keep that in mind too 
-I’m always interested in cases where a) you have a search that doesn’t fetch that much data, but b) it’s taking a long time, because that generally means there is room for a performance optimization. There are some known issues here, like :unique tends to be much slower than it ought to be (we have a project underway to change that), but often if you can isolate a search on a test page and show it to us, we can find something to tweak to make it faster.