"Public domain" refers to things in principle copyrightable but where protection has lapsed, been repudiated, or is a statutory exception (such as government works). A website is not "in the public domain". The idea that a website is "public property" is (*cough*) mistaken.
There are basically two ways in which a web interaction could be illegal. The first regards whether accessing another person's computer is illegally accessing a computer, which is a crime. Authorization essentially comes down to "permission": if the owner permits me to access the computer, I am authorized. Putting stuff out there on a web server is an open-ended grant of permission to look at a web page. That simply means that if I create a web page (with a bunch of links or not), I am granting you permission to interact with my computer to that extent. It does not create permission to hack into a password-protected subdirectory. An ordinary web crawler automates what a clicking human does.
Copyright law is also relevant, in that the stuff I put on my webpage is not to be copied without permission. Any webpage access necessarily involves automatic copying from machine to machine: in putting stuff out there for the world to see, I am saying that the world can do that level of automatic copying that arises from normal html-and-click interactions. It does not mean that you can download and do stuff with my copyrighted content (i.e., it is not an abandonment of copyright: I did not put that stuff in the public domain). Putting a web page out there in an unrestricted fashion means that you've given a certain level of permission to "copy" (at least in the automatic server-to-browser viewing sense).
I may want to impose conditions on peoples' access to my stuff, so I can impose terms on such material. For instance, I may require users to agree to certain conditions before accessing the CoolStuff subdirectory. Users then have to jump through a minor hoop and agree to those terms. In that case, my permission is conditional, and if you violate the terms of that agreement, I may be able to sue you for copyright infringement. It could then be a violation of my terms of service (TOS) if I say "you may not crawl my website" (in less vague language). A TOS gets its legal power from copyright law, because every webpage interaction involves copying (I assume that technical point is obvious), and copying can only be done with permission. You may technologically overcome my weak click-through technology so that the bot just says "sure whatever" and proceeds to illegally use my web page: I can sue you now for copyright infringement.
The robot-specific methods of meta-tags and robots.txt have no legal force. Although there is a way to say "no you may not," which is tailored to automated access, the meaning and enforcement of these devices has not yet reached the law. If my page uses NOFOLLOW and your program doesn't know or care, you (your program) do not (yet) have a duty to understand, detect and respect that tag. Prior registration is also not a legal requirement, and very many pages that are on the master crawl list get there from being linked to by someone else's web page. Again, there is at present no legal requirement of pre-registration (and there is no effective mechanism for verifying that the site owner has registered the site).
Archiving and especially re-displaying someone's content is, on the other hand, not legal. It would be plainly copyright infringement if you were to scoop up someone else's webpage and host it. You can analyze their material and somehow associate it with some search terms, and display a link to that page, but you cannot copy and republish their material. You can put very short snippets out there taken from a web page, under the "fair use" doctrine, but you can't wholesale republish a webpage. (It should be noted that the archive.org is an internationally recognized library, and libraries have extra statutory powers to archive).