Hi
Basically, you have to setup .htaccess properly for the server you are using. It has nothing to do with the site, it's about the server. Then you just tell sh404SEF whether you use a .htaccess file or not.
It's exactly the same with Joomla own SEF: you have two settings: one to enable SEF urls, and the second to tell it whether you use URL rewriting (.htaccess) or not (no .htaccess).
I cannot help you with your server really, but usually the .htaccess that comes with Joomla is fine. You may have to remove or add a line or two in it.
I can see that you get a web server 404 page if you try to access, for example, http://www.XXXXX.com/teotys/poste-clients. It may indicate that you have to look at the RewriteBase instruction in the .htacess
Either remove it you have it, or on the contrary uncomment it:
This is from the default Joomla .htaccess:
##
# Uncomment following line if your webserver's URL
# is not directly related to physical file paths.
# Update Your Joomla! Directory (just / for root).
##
# RewriteBase /
Rgds