Hi Shai,
EFF did recently go through a lot of trouble to save all of our recurring donations when we switched from Convio to CiviCRM. It was a whole lot of trouble. If you have a small number of recurring donors it would probably be less work to just call them all up on the phone and explain that you need them to re-donate with the new system. The details are murky, but the backend payment processor is the company that actually has the recurring credit card tokens and either some sort of API that's used to manually re-charge the card every month, or they charge it themselves on a cron job.
What we ended up doing is paying the payment processor like $2000 to give us the actual credit card numbers, canceled all of the recurring donations, exported the exact day each month that all the recurring donors expect their card charged, and we wrote a selenium script that we watched run once a day for 30 days that charged that day's cards. We had to hack the CiviCRM authorize.net payment processor to not validate on security code, since we didn't get those from the payment processor (only credit card numbers and expiration dates). In the end it was a huge pain but it worked. We had about 1000 recurring donations at the time.
We got some advice from Rainforest Action Network who ran into the same problem when they were switching from Convio to Salsa. The people at Salsa helped them out a lot, and I think their solution was actually very different than our solution. Their Convio account was opened way earlier than ours was so they were using a different payment processor.
I believe they were able to get Convio to transfer ownership of their merchant account to them and open up a separate merchant account for their new Salsa transactions. They just kept the old merchant account active until all of their legacy recurring donor credit cards expired, and when that happened and the donors re-signed up they would go into the new Salsa merchant account. Something like this might be possible for you moving away from Salsa and into CiviCRM, but it will probably involve either editing an existing CiviCRM payment processor or programming a new one that will let you get IPN pings from whatever Salsa is using right now to add contributions to CiviCRM.
tl;dr: It's really hard and takes a lot of work, but in some cases it's totally worth it. If you can afford to cancel everyone's recurring donations and ask them to re-sign up, this is by far the easier route to go.
