Thanks for the quick reply Daniel!
As a short term fix I added
<replace-with class="com.google.gwt.user.client.impl.HistoryImplSafari">
<when-type-is class="com.google.gwt.user.client.impl.HistoryImpl"/>
<when-property-is name="user.agent" value="gecko1_8"/>
</replace-with>
to my App.gwt.xml which seems to fix our problems as it doesn't override decodeFragment(). As a long term solution I'll attempt an upgrade to 2.7.0.
Cheers
André