I have setup the Application Links correctly between my JIRA and Fisheye installation and everything works fine when user is logged in Fisheye. When user is logged in he can see the issue when hoovering it but when not logged in he sees "Issue not found". I don't understand why we get that considering that we have browse project in JIRA open to anybody so any user can see the issues without having to be logged in.
This is probably hapening because the Anonymous Access in FishEye is disabled:
Can you try enabling it and check if it solvest the problem: https://confluence.atlassian.com/display/FISHEYE/Configuring+Anonymous+Access