Hi
First off, please make sure that the "301 redirect from Joomla SEF to sh404SEF" setting under the "Advanced" tab of sh404SEF is disabled. When this is enabled, we ask the Joomla router for a possible valid URL for the incoming request, and unfortunately the Joomla router does not do this very well (it will accept URLs that are 404s).
Then if not solved, please update to the latest development version,
from this page. In the future, you may want to check that development version (it's linked from the helpdesk main page, and from your user menu): your problem may already have been solved.
Please advise.
Rgds