The question cannot be answered (but my bet is on "No way!"): "the Internet" is a transnational entity. So two adjacent IPs might be on the opposite sides of a border, and what is legal (or at least not forbidden by law) for one might be a crime for the other.
In some South European countries chuckle, a portscan can be construed as "suspicious behaviour" -- in those same countries, if you walked by wearing a mask and a prybar, you can be detained and, lacking a convincing explanation, arrested. So-called "abstract danger of criminal conduct", allowing the inversion of burden of proof.
In such a case, you would be required to demostrate that your portscan is NOT a preliminary to an attack; it is not the portscanned that has to prove you ARE reconnoitering for an attack.
In many other countries (France, Germany and Denmark, but probably most of Europe), any "unforeseen" usage of network resources has to be cleared with the owner of same. It is of no importance that the "usage" is limited to a few bytes packet, nor that every day spammers and worms perform much greater abuse.
Also because, if you were to be permitted a slow portscan, why should everyone else be excluded? And if everyone were to run a portscan, however slow...
So, you might be onto something if you:
- offered the service to interested third parties,
- cleared it with them (obtaining probably a written permission)
...and then most of them would require that you kept their vulnerabilities confidential, of course. No public DB of open relays or Jurassic SQL servers or DB open to default password.
update/expansion on comment by mark
disclaimer: I Am Not A Lawyer (and I'm pretty fast approaching the limits of my knowledge)
The breadth of interpretation is generally mainly targeted at
allowing prosecution "in case of need" (there is a well-known quote attributed
to an Italian PM of the 19th century, "Laws are applied to enemies, but interpreted for friends").
In Italy, portscanning a system is likened to a "look at a door" - it may be a passing gaze or a deep, expert stare capable of assessing the lock's strengths and weaknesses [ http://www.civile.it/internet/visual.php?num=44650 ]. The hardliners hold that while a "gaze" is a passive action whence no intent may be gleaned, a portscan implies affirmative action to be undertaken, and is therefore more alike to looking with binoculars - you need the equipment, the knowledge and the intention to use it.
A legal analysis of the portscanner's position may be found here, but it is written in Italian legalese http://www.ordineavvocati.roma.it/Documenti/TemiRomana/GiurisprudenzaDottrinaDirittodellInformatica_2.pdf - the long and the short of it is: a guy ran a portscan and got his DSL account pulled; went to trial claiming that a portscan isn't a crime -- and lost. The commenting lawyers are more doubtful, but they admit that the contract prohibited "any improper use of the service", and portscan wasn't listed in the "proper uses" (for that matter VoIP wasn't -- and still isn't!), so.
The key point is that "intent" can be "assumed", "proved", or "disproved", and due to the lack of certified telepaths it's all in the hands of the lawyers.
In Germany the regulations instituting the Cyber-Abwehrzentrum coordination speak vaguely of "suspicious activities", which I take it to mean that if a polizei offizier has a bad hair day, sending an email with mistyped address might earn you an audit (it could be an "Act preparatory to data espionage").
Again, a good lawyer may get you out scot-free. But if a judge gets convinced you were up to no good (e.g. you did that before, are a notorious hacker, etc.), then laws exist allowing you to be locked in for some years.
(The NCAZ actually deals with threats to the State, but since they may come from individual ISPs and terminals, they have jurisdiction on individual (i.e. not a firm's) accounts too).
Simple possession of tools such as nmap or hping MAY lead to up to one year sentence (I'm not kidding you. Google 'Section 202c' of German Strafgesetzbuch on IT). So that things like this may and do happen: http://news.techeye.net/security/security-expert-acidgen-sued-for-vulnerability-warning .
Laws not too different (albeit differently worded and held in different regard by local magistrates and lawyers [this last is my opinion, of course]) are in effect throughout the European Union due to EU law uniformity, so I'm pretty confident that the situation, at least potentially, is probably not so different in countries of which I know nothing, such as Belgium or Spain.
Of late, the "early bird" interpretations of EU directives on cracking down on hackers adopted by Germany have made way into an EU law proposal (the difference being, AFAIK, that EU directives "may" be transmogrified into individual countries' law corpus, while EU laws must -- actually, they automatically are): http://www.europarl.europa.eu/news/en/pressroom/content/20120326IPR41843/html/Hacking-IT-systems-to-become-a-criminal-offence . The problem being, who says what is a hacking software and what is not?
