Matt Cutts of Google did a video answering the question How long does a reconsideration request take to process?
Matt said at the end of the video, it should not take more than a couple weeks to get a response to a reconsideration request. If it takes more than a couple weeks, he suggests you post something in the Google Webmaster Forum.
Four Responses To A Google Reconsideration Request
The interesting part of the video is not the answer to the question but how Google classifies the different responses they may give to reconsideration requests. There are four response buckets:
(1) You do not have a manual action against your web site.
(2) You did have a manual action but Google removed it after reviewing your reconsideration request.
(3) You do have a manual action against your site and still do because there are still issues with your site.
(4) Google processed your reconsideration request, which means, you are between numbers two and three. Google needs to look deeper and maybe you resolved some things but not all things. Maybe Google found something interesting they want to look deeper into.
I guess you probably do not want to get the "we've processed" response to a reconsideration request. It doesn't sound good to get one of those. Being in limbo is a scary place to be - you don't know what to do. Do you make changes? Do you wait? That is a scary thing for a webmaster.
But to answer the question above, it shouldn't take more than two weeks. Here is the video:
Forum discussion at Google+.