Google did the same thing to me on my joomla website !
It always had sef ON, but it indexed non sef urls, leaving me in great troubles, as the structure of my database and my IDs changed, Google is now calling non sef urls that do not refer to anything any more, generating tons and tons of 500 errors.
As long as the structure was the same, google calling non sef urls, wasn't ideal (duplicate content A LOT) ; but at least it worked and had a proper page displaying.
But now that the structure changed (Ids changed), non sef urls are not referring to anything any more and all it's displaying is 500 errors.
Crazy.
This is exactly as if google is indexing my website before urls are rewritten !
I more or less managed to get back on my feet.
I got back to my old ids (incredible work).
But I'm afraid you'll have to redirect manually, as :
-SH404sef can't redirect non-sef urls
-Google seems to crawl joomla websites before their urls are sef
I advise you to have a look at php redirect. This is how we got rid of some 500 errors. I believe you can do the same to redirect your pages as php redirect seems more powerful to manage bulks of urls with conditions.