The problem is when MPS creates a new site, the Search Service Account does not get assigned rights to the site; therefore,
when you perform a full web crawl, it cannot crawl the site. Hence, search is broken. I can manually fix this problem and then searches start to work.
This only happens when you create the site from MPS. If I use the STSADM command, then the service account is assigned
rights and search works.
I have confirmed the rights on the WSS 3.0 server, WSS Farm, and SQL Database. I have also confirmed "Execute As"
in the Deployment Tool and tried re-initializing. When we discovered the problem, we were running RU 7 and have since upgraded to RU 9, but no difference.