You neglect to mention how you are accessing the newsgroup. In general,
however, newsreaders can only search header contents (not body) unless you
have downloaded all messages, not just headers. In Outlook Express, this is
the "Subject" field, not the "Message" field.
I just got one (message = cookie jar, dates between 2 Dec 1998 and present)
to work there. Beware that it appears that they have snipped the searchable
history to the same 30 days that they are retaining posts for because of the
Swen worm/virus nonsense. As Cal note, http://groups.google.com is probably
a better bet.