Cost vs Benefit mitigates paranoia in my experience. If you can outsource and save a bunch of money doing it (or free up critical internal resources) its amazing how security can become less important and/or more easily satisfied by appropriate business/service agreements.
The other aspect to consider is the big picture. What else is outsourced? E.g. if your email is outsourced, that's likely far more critical. What about faxes? Or backups? Or phone calls? Or your internet itself? In this bigger realm, the bug tracking system might be the least of concerns.
Finally, just who is "someone else"? Is there a competitor motivated enough to find the outsource vendor, break their security and get into your bug system? And is that really so much harder than someone breaking into an internally hosted solution?
Yeah, I've worked with companies that have outsourced bug tracking (and svn) and been very happy with the results. The business benefits and far lower costs of outsourcing to reputable companies that do this well vs doing it internally have offset the perceived risks many times over.
Good luck!