I'm not sure if this is a 10.4 problem as well as 10.5, but it's something I've only just noticed.
I installed OS X from scratch, after backing-up my data. I then imported my old mailboxes into Leopard's Mail program using the Import feature.
So far so good. But when I used Spotlight (or even Mail's own search box) to look for an old message I knew was there, it didn't show up. Only a new message I'd just received showed up. In fact, my tests showed all imported messages slip under Spotlight's radar, even after I used MainMenu to rebuild Spotlight's index.
The solution was to use the Rebuild function under the Mailbox menu in Mail. Hey presto -- everything is now indexed, and old messages can be searched for. I assume that this forced Mail to reprocess the messages, thus allowing Spotlight to, erm, spot them.

