When I get the message "Your search criteria expired", if I hit the browser "back" button, I'll get a warning about resubmitting a form from browser cache -- and if I refresh it will resubmit the form and I'll get the results of my Saved Search preview again. It's a weird thing. I feel like there's some sort of browser/session timeout and if you doddle or take too long it expires and you have to resubmit the search. Then you're good for a while.
I also get this same "Your search criteria expired" message on Saved Mass Updates. And in that case, I have to clear my NetSuite browser cookies (two of them), sign back in, and then it'll work the second time. Not sure why, but it's been an ongoing thing for maybe 2 years, where the Saved Search "criteria expired" I feel like has been a "forever" thing.