Hi Matt,
I'm able to create a medium trust environment on a local dev machine by adding this to system.web section of Web.config:
<trust level="Medium" originUrl="" />
In my testing the search index is built fine so I'm not convinced this is a medium trust issue though it does follow a previous medium trust issue I worked through with you. The previous problem is solved and something else is going on now.
Please clear your mojoportal log, then do a search, then scan the log for any errors or messages and let me know what you see.
If this is a new site the most likely problem is it can't write to the /Data/Sites/1/index directory
I would check the permissions on Data and its subfolders again.
Best,
Joe