We are running JoomFish + JoomSEF at many sites of our own with no problems. So I believe this might be just misconfiguration. Or some other piece of Joomla-related code interfering. You have named the problem well, it is quite difficult to make work so many pieces of code from so many different authors. That is both advantage and disadvantage of open source.
However, not to be pesimistic, it works in most cases. However, there are some minor cases when it does not. Sorry for those. Just do not ask us to solve such for you (this is ment generally not to you personally) for free. :-) But you can always get a paid support and so far we have never failed to find a solution to a problem. Mostly it is just matter of time spent on that. If the default setup does not work, you can try other solutions. If you think our is best and want to use it, then buy a support. The good thing is, you have choice. ;-)