Yes, all the time. I subscribe to a lot of mailing lists and noisy "stuff", so I use stars heavily to flag threads that are important, so they don't drown in the noise. If I need to revisit a thread that is more than a day or two old, and I know it's important (and therefore should have been starred) I just go straight to the "starred" view. Only if it isn't near the top and easy to find to I fall back to keyword search.
I've also started using labels more lately as well, and find that pretty handy. Anything sales related, for example, gets a special label. This is especially handy for unsolicited inbound leads.