I can confirm for you that this is an issue in CRM 2011 (still an issue as of Rollup 14.) Wish I had an easy solution. Lazy way around it is to create a do-nothing team, with no security role assigned, and just put every user in it. This is a work-around, not a solution, but it will make the issue go away. Not 'elegant' but it works.
The alternative, as you suggest in your post, is writing custom FetchXML for each query you need this on but that defeats much of the benefit of the Advanced Find Query tool and makes long term maintenance and administration more difficult.