A good way to handle that is to make a XML site map that translate old URL to new URLs, and a HTTP module that makes a permanent redirect to the new URL based on the information in the XML sitemap.
In a project I was working on where the robot link format in 4.62 needed to be replaced to the FURL format in CMS 5 R2, I created an HTTP module that extends and inherits from the Friendly URL Rewriter. In effect it converts a link from default____1.aspx to default.aspx?id=1 if found, and then the base FURL rewriter does its job from there.
This solved the problem for me with old external links that Mattias speaks of, as well as internal links that weren't properly converted with the Migration tool (- unfortunately it isn't quite perfected yet!)
Hope it helps,
/Marten
Our website (epi 4.61) has urls in the format templates/default___1.aspx
I can se in admin mode that it is posible to change it to other formats. If I change it to /page1/page2 will there be any problems that i have to consider? Is there more settings I have to change to make it work? Does it work to index the site with a 3-part search engine with that url-format?