It worked well and smoothly when I changed my permalinks' structure, taking out that awful "/index.php/" from it. It is fluid and transparent to visitors. All I had to do was to include a single url to url redirection, checking also the "regular expression" box.
That was exactly what I needed, so present permalink structure works as if the old one was also valid. No lost links, no lost search engine results. Worth a PayPal donation!
My site: Yogaforum.org