I remember I and many others starting to use them for exactly that. Look at this comparison (not that early is starts at 2004 while google iirc started to see usage at 2001)

http://aautar.digital-radiation.com/blog/uploaded_images/goo...

Some other search engines were even more heavy handed on advertising.