To give some news. Well, I have been working officially since February 9 as a J2EE architect at Linagora, an IT company specialized in open source solutions. I have been working quite a lot since then and I'm still looking (albeit passively) for an appartment. My best bet for now is to move to the building where I was living before. It's would be way easier. It's France so to keep it short about all the documents you have to give to proove that you are a good person that will be able to pay, you need to provide your last 3 receipts of your last apartment rental, your IRS copy, your last 3 salary receipts (your net salary must be 4 times the amount of the rental), an employer attestation, a bank certified check for a sum equivalent to 2-month rental, a check for the real estate agency and a morale person as a caution. Now imagine what's like when you have only been working for less than a month ?