I've seen this issue with two MOSS 2007 implementations now - end-users report that performing a search from a MySite returns Access Denied. The typical scenario is that a user will do a People Search for an individual, click through to the result which puts them on that individual's MySite, and then from that Mysite they'll try another search for a different user. At this point they get an access denied error or other weirdness.
The solution to this issue is to go to the Shared Service Provider in Central Administration, click on My Site Settings, and ensure that the Preferred Search Center URL is correct (i.e. that it points to the desired Search Center, typically the one used in your main SharePoint portal - like http://[sitename]/searchcenter/Pages/)
The worrisome aspect of this is that both times I've seen this issue, it has happened after a new site collection was created, and that new site collection's Search Center URL got plugged into the SSP's Preferred Search Center setting. One of my colleagues theorized that this setting points to the most-recently-created Search Center (and a new Search Center is created each time you use the Collaboration Portal template for a new site collection). I could not find a setting in Central Administration, or at the time of creation of a new site collection, to prevent this from happening.