Setting this up for the first time was a little challenging. I couldn't figure out why no matter what combination of settings and credentials I gave the search service it wouldn't crawl the public folders. I tried crawl rules, complex URLs, content access accounts, but eventually I gave up focusing on SharePoint options and started to look more closely at what was happening at the other end - what was exchange doing?
I had already checked the IIS settings for the public virtual directory and it showed that Basic and Integrated Windows Authentication were both enabled, so I next tried to hit the public folders URL with it in my local intranet zone so that windows would pass through my credentials automatically - just like we set up SharePoint all the time. Anyhow, I realised that no matter what I did with the IIS settings I couldn't get to the page without first entering my credentials on a form based login for OWA. I googled some more to find that although I was setting the authentication options in IIS, there are some additional settings in Exchange System Manger.
If you open ESM, then expand Servers, <server name>, Protocols, HTTP, you'll find the exchange virtual server, if you right click on the virtual server and select properties on the second tab there is an innocuous little box that says "Enable Forms Based Authentication".
So it didn't matter what I did in IIS Manager because it was overridden by the settings here. Well, someone helpfully pointed out in a forum that you can in fact create a second virtual server and set that to work without Exchange FBA. Yay! That's what I need, our existing users can keep their interaction the same on the current URLs, we'll create a new virtual server and set that not to use Exchange FBA, just Windows Integrated authentication and hopefully our crawl will work fine.
So the crawl has reached the end and 18,224 items are indexed and searchable in milliseconds. Lovely. I just need to make sure I've put all the settings back how they should be (you did make a note of all those changes you made as you fiddled in IIS, Exchange & SharePoint didn't you?) and once I'm happy that the URLs are accesible in the right places the job's done.