Search not returning result for other domain users

I have a strange situation when users from other domain does not get any results when they perform a search. Here's the scenerio:

1. I recently upgraded the farm from Sp2007 to Sp2010.
2. Crawl jobs all completed successfully
3. Our domains:
   - myco.com
   - eu.myco.com
4. User from myco.com can search fine.
5. Search performed by user from eu.myco.com return nothing... envon on simple search where I am sure they have access to. Also, they didn't have this problem in SP2007.
6. These eu.myco.com users does have access to the sharepoint sites.
7. It is similar to the issues describe in this discussion: http://social.microsoft.com/Forums/en-US/partnerofficesharepoint/thread/b547461a-e47b-4b54-980d-d6b36e244bae.  The fix was to add the search/servcie account to the Windows Authorization Access group.
8. In my case, I need to add the service account to the Windows Authorization Access group on ALL the domains.