If a bunch of your url's are already indexed, when people click them they will automatically 301 to the new URL. Quick way to test it, find one of your links in a search engine, turn on your sef, then click it. That's the whole point of it building the links in your DB, so you don't have to do it manually.
If you want all of your links created into your db, just use a tool like
gsitecrawler.com
and it will crawl every url on your site, it will be finished in one shot. I have sites with 10,000+ URL's and I crawled them with it. Besides, having the sitemaps that the crawler creates also helps the SE's find your stuff better.
Just make sure you do it right the first time. Make sure you configure it correctly so you don't have duplicates. If you have SEF URL's indexed, and you change them, you'll get tons of 404's. Best to do your homework up front.