After lots of unsuccessful debugging to try to find out where Firefox fails to run as expected the component was modified to output the exact same markup as the test page provide with RSH library. Even then the component would not replicate the behaviour found in the test page.
Finally the only difference that could be found was in the response headers for the page load. JSF sends no-cache headers thus forcing the browser to discard the history state saved in the previously loaded page.

The conclusion is that JSF is not a compatible environment for RSH+Firefox.

It turns out that our CachingHeaderPhaseListener registers a phase listener that adds the cache invalidating headers mentioned in previous comment. Removing the phase listener makes Firefox and IE work as expected.

Tried to re-implement the current functionality using HTML5 techniques (using localStorage and history API). Unfortunately the history API that ensures a solid detection of back/forward navigation is supported only in IE10 and higher (and of course Safari, Chrome and Firefox). See also http://caniuse.com/#feat=history . Only the localStorage API is available since IE9 and up: http://caniuse.com/#search=localStorage .

Here's the original intent for this component: ICE-5685. Also the reason for its creation: ICE-4794.

Disabled the sending of no-cache headers when navigation notifier is present.

Applied fix to maintenance branch as well.

ICEfaces4 trunk rev. 41838:
1) is resolved (verified in Chrome36, IE10, FF30).
Issue 2) still can be reproduced in all browsers after enabling the ace:panel on start.xhtml page.

IE10:
Message: Object doesn't support property or method 'exec'
Line: 30
Char: 272
Code: 0
URI: http://localhost:8080/navigationNotifier/javax.faces.resource/util/ace-jquery.js.jsf?ln=icefaces.ace&v=4_0_0_140723

FF30:
TypeError: ha[h].exec is not a function
http://localhost:8080/navigationNotifier/javax.faces.resource/util/ace-jquery.js.jsf?ln=icefaces.ace&v=4_0_0_140723
Line 30

Chrome36:
Uncaught TypeError: undefined is not a function ace-jquery.js.jsf?ln=icefaces.ace&v=4_0_0_140723:30

Modified Really SImple History third party library to use latest JSON library. This avoids having the Object and String prototypes modified (which caused part (2) of this issue).

Verified with IF4 trunk rev. 41846/ Jenkins build 532 in IE10, FF30/31, Chrome36.

Our test application and the showcase demo both expect that notification will occur (showcase) or a counter will be incremented (QA test app) only when the Browser Back/Forward buttons are used.

Issues:
IE 10 - QA test application passes consistently but the in the showcase application it passes about 50% of the time. In fact, every second time.

IE 11 - The tag does not function at all in either application.

FF 31 - The notification is triggered when the page is reloaded, as well as when the Browser Back/Forward buttons are used.

The QA test app can be found at:
http://dev.icesoft.com/svn/repo/qa/trunk/Regression-Icefaces4/Sparkle/Manual/navigationNotifier

Re-implemented icecore:navigationNotifier to use HTML5 features. Only the browsers that support HTML5's new history API will actually be able to detect back/forward navigation.
Here's the list of supported browsers: Chrome, Safari, Firefox, IE10, and IE11.

Rev. 42540: in the QA test application, the component is not fully functional in Chrome; the counter is updated only when clicking to go back, and not when clicking the "forward" button; not an issue in IE10/11 or Firefox31.
http://dev.icesoft.com/svn/repo/qa/trunk/Regression-Icefaces4/Sparkle/Manual/navigationNotifier

Improved navigation and page reload detection algorithm. Also worked around Chrome's limitation in updating the history state during page unload.

Verified with rev. 42551 in Chrome37, IE10, FF31 in showcase and QA test app.