Unless I see that a site is banned totally, i never stop working on link building or adding content for that matter. The site came back in 1 month and 10 days. It took a year on another site once. So there is no fixed time frame so to speak.
How long does it usually take you to go from 0 to ranking for this kind of volume?
No Idea. I don't track that too well, but it is not constant. Sometimes it happens in a month, sometimes longer, even though I follow similar routine on all my sites.
Its easier to get such volume when a keyword has massive Broad Match traffic. You get a lot of high volume sub pages to work with.
And how much do you budget for your linking work?
My Budget is "unlimited", because, I know that, no matter how much I spend, it is never enough, and also the return is always positive.
I cannot work with a Budget in my link building campaigns since these are no micro niche sites where I can only get 200 UVs a day with the top position and the return is small.
The Major constraint is not the budget but finding relevant sites to link to me, whatever the cost. for that I have an unlimited budget.
Web 2.0 and similar stuff are my very very low priority links that I add just to increase the diversity and for lack of other links.
When your site comes back, does it usually just pop back to where it was or better, or do you basically have to start working your way up again.
Usually better, because I never stop working.
On this site, as I mentioned, all my pages and posts were nuked. Suddenly today, all my pages and posts are back, and most of the positions are better if not the same.