Okay. Where to begin. When you set up a Webmaster Tools account, essentially a new entry is made into a database and various bits of data needs to be collected such as site performance, and so on that simply will take time to populate. When you just create the account, that database is essentially empty. As most of us know from experience, the Webmaster Tools is at least 2 days behind and sometimes the metrics can be 3-4 days behind. So doing anything in GWT is just plain a waste of time until your metrics catch up closer with reality. This can take about 2 months. This is why GWT says there are no security issues with your site.
Next. There is a slight disconnect between being indexed and what you see in the search engine results page (SERP) with some elements being somewhat real-time and others not so much. Any effect, other than the SERP link and cached page, such as placement and other elements, you can count on taking some time to clear. Partly because there are in effect two systems though not literally, but say, two tracks of the same system. It is simple enough to take a freshly indexed page and update the SERP link if all fits within certain parameters and make it what you want. However, adjusting the various metrics and calculations that effect things such as SERP placement and what not take much more time especially since some of the metrics behave exactly or nearly like a rolling average.
For your "this site may be hacked" notice. We know that these originate from at least two places and potentially one more. I will explain these.
The Google Toolbar has within it a rudimentary anti-virus product that protects browser users from issues resulting from compromised sites. I say rudimentary because it is not a full anti-virus as we think, however one trimmed down only to those issues seen in browsers. The Google Toolbar has the opportunity to report any issues no matter how severe or even if it is a false report to Google that then can mark the page as having been potentially compromised.
Another more severe source for Google are black-lists and believe me, Google checks these black-lists constantly for sometimes a very real-time effect. If your site is found within a black-list, Google can take several actions including temporarily delisting a site. In this case, the root domain home page may still be listed in the SERPs with a warning that the site may be compromised and all other pages will be no where to be found. In this case, the entire site is marked as compromised and this condition will not lift until it is removed from the black-list.
The final source is the ability to check any fetched page immediately for indications of having been compromised. There are theoretically two ways this is done. One, the page is fetched in the traditional way and the source is checked within a search engines systems. The other is to use an anti-virus product to fetch the page and the page is checked withing a specialized system. Both are possible, however, no-one except someone within Google can say this as a fact. But please know that this is a very old process, well over a decade, that is still used and works extremely well. I would not be surprised if such a system exists for confirmation at least. I have worked with these systems for search engines before and can confirm they exist.
Please understand that because the webosphere is so vast, that even setting a trigger within a search engine, any search engine, will mean a delay of some sort. Google is no exception. Because Google has been so successful at indexing a huge portion of the webosphere, Google can be particularly slow. For example, changes in SERP performance can take 6 months to a year to change after re-doing a site.
You will simply have to be patient. However, you can check to see if your site is listed within a black-list and clear your site from the list if possible. My favorite resource to recommend is: http://mxtoolbox.com/blacklists.aspx I would suggest checking this resource. If your site is listed, follow the instruction/path to getting your site removed from the black-list. Each one has it's own set of procedures and some you will not be able to effect at all. Do what you can and do not worry about the rest. Search engines know the effects of these black-lists and prefer the more real-time lists which is to your favor. So for any list you may be on that takes a year to clear, please understand, Google is not likely looking at these in regard to your issue, though they may use them for trust metrics.
