If you return your site to the original state that it was in prior to the malware attack, Google should rank it again near the same position as it was in before. I had this happen with one of my sites where I enabled a WordPress Plugin that put up an "under construction" type of page. Google deindexed the site and I freaked out at first. However, all I had to do was disable the plugin and add 1 new post to the site and I was indexed again and ranking #1 for my main keywords again. I believe that patience is key here.
peculiar things are happening in Google SERP !!! Google has de-indexed a few more links of mine and re-indexed the homepage w/o WWW !!! I clearly mentioned in webmaster's tool 1 year back that my choice of index is with WWW. Now they will put the home page in content duplicacy and de-index it again check this
http://www.google.com/safebrowsing/diagnostic?site=footyfree.com Google says the last time suspicious content was found on this site was on 2011-08-26 If you have removed all suspicious content.. then go for a reconsider request.. They will take around 10-15 days to review your request.
I think it's not Panda that hit your site. As we all know it, Panda is up to quality content of the sites. You site have loss traffic and backlinks because of the malware that you didn't resolve much earlier. I suggest you create more quality content for your site then, do your link building techniques.
It could be temporary, at least you have not been removed from the index entirely, or given a warning "that this site is dangerous"
If your content is copied from other site or you have done plagiarism on your site then there is 100 % chances that you have hit by panda update
I had a malware issue on a site and it took almost 2 months to get back to where it was before the attack. Keep on linkbuilding as normal.
That could be possible if you hadn't mentioned the malware attack. See sites with malware attacks pose a threat and threats are something that Google doesn't like. That could be the reason. heck if your pages are still indexed or have they been de-indexed by Google as well?