Hi,
Make sure you have the "Use apache mod_rewrite" option enabled in your Joomla global configuration.
These URLs are usually created by search engine bots that have still indexed the old index.php/ links on your site. Which version of JoomSEF do you use? The 3.6.5 version shouldn't store such URLs in database anymore.
You can also enable the "URL Source tracing" in JoomSEF's configuration on Advanced tab, so the trace information will be stored with each new URL - this will help you find out why the URLs are created as the URL's origin, referer and user agent is stored.
Best regards,
ARTIO Support Team