Why is 有 (yǒu) the only verb that requires 没 while other verbs can use 不?
The Story of 没

As other commenters have noted, looking for logic in language is almost always futile. No natural language is logical. But there is a historical logic to language development; even if the existence of a phrase is a historical accident, it's sometimes interesting to see when that "accident" took place, and why.

Such is the case with 没. One interesting fact I learned from all this that contradicts what some others have said in their answers: 没 is not a contraction or shortening of 没有, at least not originally. MarkDBlackwell is right to point this out in his answer. The development of both words is slightly more complicated.

(All of the following comes from Xu Shiyi's excellent paper "否定词‘没’‘没有’的来源和语法化过程". To save time, I will not differentiate between places where I am quoting, summarizing, and expanding the original text. Apologies to the author; all errors are my own.)

The History of Negatives in Chinese

Before beginning, it's important to distinguish between two different categories of negative words: negative adverbs (否定副词) and negative verbs (否定动词). For our purposes, the former category is any word that can be put before a verb to negate its sense; the word 不 in modern Chinese is a good example. Negative verbs can stand alone at the "center" of a predicate (谓语). The word 没 is sometimes used in this way in modern Chinese. For example, in the sentence, 


  屋子里没人.
  wūzi li méi rén
  There is no one in the room.


没 is acting as a verb, not an adverb modifying another main verb. (The use of the word adverb is not exactly right here, by the way, because the category 副词 doesn't exactly correspond to the English category of adverbs, though it's pretty close.)

I'll also be making a distinction between the use of 没 as a "full-fledged verb" (corresponding to its reading "mò" today,meaning "to sink, to be covered") and its use as a negative verb.

Previously (in the oracle bone inscription days), Chinese had many negative adverbs, such as 不 、弗 、勿 and 毋, and later (during the Zhou and Qin dyansty period) added several more, like  非 、匪 、微 、无 、蔑  and 未. Both 无 and 蔑 were themselves negative verbs also, and both had the same meaning as 没有 does today.

没 on the Scene

The first textual evidence for the existence of 没 (as a verb meaning to sink/submerge) is in the Tang dynasty, but various pieces of evidence which I will not repeat here imply that 没 was already being used as a negative verb (not a negative adverb) before the Tang period.

The use of 没 as a verb meaning to sink into water gradually extended until 没 meant to disappear or lose. From a phonetic perspective, though, there is no link between the use of 没 as a full-fledged verb and its use as a negative. (Recall that two different pronunciations of 没 exist today which enforce precisely this difference.) Indeed, many experts have assumed that 没 originated as a negative word because it sounded the same as 未 (wèi, which is still used as a negative adverb today to mean "has not yet").

The author of this work, though, prefers to trace the connection between 没 and 无, which, as I pointed out above, has long had the same meaning as modern "没有."

Phonetic History of 没 and 无

Our knowledge of the phonology of middle Chinese comes mostly from a Song work called &lt;广韵> Guangyun, which listed characters according to rimes [sic]. To indicate the pronunciation of a word, the dictionaries of those days used something called the 反切 method, which split a character up into two other characters, one representing the syllable onset and one representing the rime (rest of the syllable). Wikipedia's article on Fanqie quotes an example from Gari Ledyard of how such a system might work in English: we could encode the pronunciation of the word sough by using the two words sun and now, to show that the word starts with an "s" and ends with the same sound as the word "now." (I am omitting many details.)

These books also come with a table of rimes so that we know basically how the various consonants and vowels were articulated in those days. There were two different syllable onsets (called 明母 and 微母) which sounded similar (the former corresponds to modern initial "m", the latter variously to "w", "v" or "m"): 没 was 明母 (cf. modern méi), and 无 was 微母 (cf. modern wú). Various historical clues allow the author to conclude that the popular pronunciation of those two words (as opposed to the possibly literary pronunciation in the Guangyun) was the same. At that time, 无 also had the meaning of "to lose" when used as a full-fledged verb. This similarity, combined with the at-least similarity in sound, led to an eventual mixing of the uses of 没 and 无. By the Song dynasty, these two words were being used interchangeably. By the Yuan/Ming period, the process was completed, and 没 had replaced 无 as the negative verb meaning "没有."

But what about 没有?

The uses described above all still involve 没 as a negative verb. In fact, the above change also influenced the development of 没 as a negative adverb. 无 could always be used as a negative adverb in addition to being a negative verb, and the compound 无有 had always existed because 无 was viewed as being the direct negative of 有. As 没 gradually replaced 无, so too did 没有 replace 无有. (The form 不有 is attested, but was gradually superseded by 没有 as Chinese negative adverbs consolidated over time.)

There's more to be said about the process by which 没 and 没有 became fully gramaticalized, but I'm out of time and will have to come back later. Will be happy to post more if you're interested.