Some more thinking on this:
Humans, elves and orcs should probably be closely related, coming from the same progenitor species and differentiated largely by their evolutionary response to environmental factors, both mundane and magical. I say this because of the existence of half elves and half orcs. One wonders, though, what a half elf/half orc would look like. Haflings are often linked closely with humans -- do they belong in this group?
Your various underground -- but not underdark -- dwellers probably come from the same basic progenitor species as well: dwarves and goblins in particular. That'd they';d be competing for resources once the races reconverged would help explain their antipathy.
Giants and giant-kin should certainly all flow from the same stock. More magical giant types need to have developed in areas with both extreme environments and high magic levels, but then I like the idea of linking extreme environments and high magic levels in general - -something abou the interaction of magic and geography/weather/etc... always suggest "turning it up to 11" to me.
Not every species needs an evolutionary niche or progenitor. Somehwere down the line, there are going to be civilizations where some members master magic. Dragons, illithids and of course humans and demi-humans would certainly toy with magical genetic engineering, and your kobolds, gnolls and other very animal-like creatures likely result from such experimentation. Truly strange monsters may be simple mutations, the results of experiemnts, or have evolved in truly extreme environments with high magic levels -- take a look at some of the beasties that exist in the deep oceans, for example.
I like the idea of magic as the functional equivalent of the Earth's magnetosphere. It changes over time, occassionally even flipping, going through its own cycles, which can cause these events that lead to massive evolution or mass extinctions. There are palces where it is more powerful than others and has an unsual affect on people and things around it. It can be tapped. It infuses and interacts with certain materials and base elements.