Dan,
This is probably coming too late for you, but perhaps others can benefit. I run a private Mailman list with approx. 1000 members, and had exactly the same need -- it's hard to get much value from 16 years worth of archives that can't be searched! I was unable to find any reasonable add-on archive search solutions for private Mailman lists running in a shared hosting environment. (There are several available search mods such as HT:dig or Swish-e if you're running on a dedicated or VPS server, where you have exclusive control of the entire Mailman environment and are thus able to install patches and add-ons. Likewise, there are free services such as Nabble that will create very nice searchable archives, but only for public lists.)
With one exception, I was also unable to find shared hosting providers that offer searchable archives as a standard feature of their Mailman offerings. One key reason is that many shared hosting companies offering Mailman do so only because it's included within cPanel, the most popular user account control panel app. In general, if you're installing a Mailman list from cPanel, you get whatever standard version and configuration of Mailman that cPanel currently supplies. Hosting companies usually seem reluctant to make custom mods to cPanel apps, probably because it complicates updates to new cPanel versions. Since archive search is not a standard Mailman feature, you're unlikely to find it on cPanel-based shared hosts. (As an aside, you probably want to avoid cPanel-based Mailman configurations anyway. As I understand it, you're basically running Mailman as a private app within your account, and are thus subject to any applicable CPU and per-hour email sending limits. It's very easy to hit these limits with larger and/or fairly active Mailman lists. And because Mailman doesn't provide throttling controls, many companies simply prohibit the use of Mailman on their shared hosting plans. Instead, they steer you towards much more expensive VPS or dedicated server plans.)
The good news is the exception I found: Dreamhost offers Mailman as a no-cost feature of its shared hosting plans. They don't run cPanel, instead using a custom control panel developed internally. All discussion lists run on a centralized Mailman installation on a separate server that is custom-configured to handle even high-volume lists. That server is exempt from account-level email sending limits, so posts to our 1000-member list are received by all our subscribers almost immediately. Best of all, Dreamhost provides automatic archives that are fully searchable! They run nightly cron jobs that reindex the archives to incorporate new posts, so the only content not included in archive searches are posts made that same day.
In general, we've been very pleased with Dreamhost's Mailman support over the last four years. We had 12 years of historical monthly archives, which they willingly imported into our account without charge. We've had very few outages or blacklist/delivery problems, and those few were resolved quickly. However, in the interests of full disclosure: About six months ago, we suddenly started facing an almost continuous series of problems - and unlike our past experience, their support team seemed unable to make lasting fixes. We're pretty tired of all the ongoing excuses and pleas for patience, to the point that I started looking for alternatives (that's why I know there aren't many out there).
Fortunately, these problems appear to be system-wide and are affecting every Mailman list - not just ours. Dreamhost is currently in the process of installing all new hardware for their Mailman server, which they expect to address all the recent problems when it's completed within the next week or two. So as of today (1/16/2015), we're staying put and hope to see a return to the smooth sailing we've always enjoyed before.
Sorry for the lengthy note, but hope this helps you and/or others looking for an inexpensive shared host with solid Mailman support that includes searchable private archives.
