Does ubiquity "unproper" a noun?

Over at Bourne in Alaska Jon Bourne wonders whether or not we can stop writing "Internet" and "Web" and just refer to them as the "internet" and the "web." That depends. Are they proper nouns? Well, yes, at least at one point in their existence. As most geeks know, but the general public may not, the Internet referred to a network created by ARPA (now DARPA) in 1969 called ARPANET. In 1983, then first TCP/IP wide area network went live on what would become NSFNet. As other networks joined to NSFNet, it became known as the Internet, due to the fact they it was linking many different networks, thus the "inter" part of the name.

While it is traditionally considered a proper noun, and often written as "the Internet," there are publications (more so outside the United States) that regularly use the lowercase. Wikipedia has this to say

Historically, Internet and internet have had different meanings, with internet being a contraction of internetwork or internetworking and Internet referring to the International Network. ... The distinction was evident in many RFCs, books, and articles from the 1980s and early 1990s (some of which, such as RFC 1918, refer to "internets" in the plural), but has recently fallen into disuse. Instead, the term intranet is generally used for private networks.
http://en.wikipedia.org/wiki/Internet#The_name_Internet

Wikipedia also points to IBM's TCP/IP Tutorial and Technical Overview, published in 1989, which stated

The words internetwork and internet is [sic] simply a contraction of the phrase interconnected network. However, when written with a capital "I", the Internet refers to the worldwide set of interconnected networks. Hence, the Internet is an internet, but the reverse does not apply. The Internet is sometimes called the connected Internet.

I would say "Internet" still refers to the world-wide connected network. As to "Web" I've never really thought about that one..and never knew it was supposed to be capitalized. I would say that since "Web" is actually a shortening of "World Wide Web," a noun which refers to a specific thing, namely the system created by billions of interconnected web pages, then it would be capitalized. But you probably noticed that I wrote "web" in the last sentence. Why? It felt natural. A "web page" is not "the web" A web page is part of the Web. I guess in the use as a noun, "Web" would be capitalized. In use as an adjective, i.e. "web page" it would not be capitalized. However, standard usage in English would seem to indicate that adjectives derived from proper nouns would retain their capitalization.

At the moment, no examples come to mind of common nouns in our language that used to be proper nouns. Someone who is more into literature probably could.