We’re currently in the process of rolling out some new vastly improved search code (more details in a future post). This code will allow fast searching across all message headers (from/to/cc/bcc/subject) and message bodies, across all messages in all a users folders. Finally!
Unfortunately this process will take a week or two to complete, and in the meantime searching in the new AJAX UI on http://beta.fastmail.fm will be broken for most users. This doesn’t affect users using the regular interface at http://www.fastmail.fm
Sorry for any inconvenience, we hope to get it fully working ASAP.