Hi,
First make sure that everything is enabled in JoomSEF's Control Panel in the SEF Status box.
If you use caching, the URLs may be cached and when you purge or delete them they are not visible in JoomSEF's URLs Manager, but their cached version is still used. In such case you need to clear the caches, so the URLs get recreated.
If that doesn't help, please post some examples of URLs that are not SEF.