Do you mean that literally - sometimes it works and sometimes it doesn't? Or do you mean that it seems to be more effective on some images than on others?
If you mean it literally does not work sometimes, try deleting the Preference folder. That's the one where you have to do a search for both the Preference folder and a .plist file. I can't remember where they are in OS X, though. Sorry.
If you mean that it seems to be more effective on some images than on others, you might need to change your technique. There was a very recent thread on using this tool. Some people have found good ways to deal with red eye through methods other than the red eye tool in Elements. Do a forum search for 'red eye' and I think you'll turn up quite a few options. What one person is very comfortable doing seems clunky to somebody else. You can read the various posts and see if you find something you like.