I got a masters degree in computer science in 2012 and worked in Microsoft since then. I'm returning to get my PhD starting spring 2017. I would like to apply for the NSF grad fellowship but having been out of school for so long and not being in school at the time of the application, I'm not sure who to ask for references. I have exchaged a lot of emails with my potential advisor on possible research directions and he will be reviewing my application but I'm not sure if that's enough for him to write me a letter. For admission, I got letters from my former professors but I'm not sure if those will be strong enough. I have a really strong research proposal. (At least thats what my potential advisor says) Do I have a chance without strong reference letters?
I have reviewed for the NSF GRFP before, including a few applications from students with extenuating circumstances.
Your potential advisor can still write you a reference letter. I have seen some first-year graduate students get relatively strong reference letters from their new advisors. The advisor writes their impression of the student based on the first 3-4 months of working together, plus the student's application materials to the graduate program if they were particularly strong. The best thing your new advisor can do, though, is attest to the level of support you'll get from them and the university for your research project and training endeavors. If they can speak to the feasibility of your project and how it potentially ties into the work that they're already doing in the lab, but still how it stands independently, that could go a long way.
And yes, your other recommendation letters should be from those former professors, who can speak about your scholarly promise. The best thing would be if one of them could address the gap in some way and confirm that they are confident you are passionate and that your time away only renewed your passion for graduate school, or whatnot. A reference writer who believes in you and who you provide with a resume and a statement that attests to this might be the best person to do this.
If your supervisors at Microsoft were not PhDs and did not do research they are not suitable references, so don't submit any from them.
However, I would also consider whether you might be eligible to apply next year, and consider waiting to apply in fall 2017 if you are. The NSF says this:
Applicants who have completed more than twelve months of graduate study or have earned a previous graduate or professional degree are eligible only if they have had an interruption in graduate study of at least two consecutive years prior to November 1 of the year the application is submitted. To be eligible, applicants must have completed no additional graduate study by August 1 of that year. Applicants must address the reasons for the interruption in graduate study in the Personal, Relevant Background and Future Goals Statement.
It sounds like you might be eligible next year as well, given that most school years don't begin until after August 1. You may be more competitive next year as your advisor would've known you for a year and you may also be able to get one other reference letter from someone at your graduate institution. Since you can now only apply for the NSF GRFP one time, consider when is the best time to apply.