Returning to grad school after several years in industry, who to ask for references for NSF graduate fellowship?
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.