I should write an update since this one got a lot of visibility. To keep it short, I got accepted into graduate schools that required recommendations.
My earliest application deadline was at the end of December, so I sent out e-mails to my past professors in August and September. One declined but two responded enthusiastically. Most applications requiring 3 recommendations, I had my boss's boss in my unit write one for me as well. He could at least speak for my character, performance, and professionalism.
I sent these writers my CV, unofficial transcripts, statement of purpose, and list of graduate schools that needed these recommendations. In that list, I included each school's application deadline, which specific program I was shooting for, and a short note why I chose each schools.
The tone of the e-mail was akin to coming with "hat in hand", being honest with the fact they probably do not remember me, and offering to send the mentioned documents for them to decide if they would write a positive letter. I didn't outright ask them if they could write a recommendation, but if they would simply consider it given more information.
I've read so much horror stories about writers not responding or sending their recommendations on time, but I experienced none of it. These writers were awesome and I'm extremely grateful for them. Every time I got an acknowledgement that a recommendation was received, I would send an e-mail out thanking them and attached an updated list of schools still needing recommendations.
Thanks for all the help and comments in this thread as well.