Have you ever had to create a Saved Search for a record type that's not available in the "New Saved Search" page?
Well, there are some workarounds to that limit, and here's an example.
NetSuite doesn't allow you to directly create a Saved Search for Messages, but there actually is a Message-type Saved Search; it's just not displayed on the New Saved Searches page. You can access it by using this link: https://system.netsuite.com/app/common/search/search.nl?searchtype=Message
If you pay attention to the link, you will see a parameter "searchtype". In this case, the type is "Message". Another record that works is "Location". Try different record types to see if they also work!