A while back the world was taken by storm when it was announced that long time rivals Sonic and Mario would be meeting for the first time in Mario & Sonic at the Olympic Games. This announcement was not made by chance or because someone thought it up.
In August 2006 Shigeru Miyamoto went on record stating that Nintendo had conducted a poll regarding which characters should be in the hotly anticipated Super Smash Bros. Brawl with Sonic coming out on top as the most sought after character along with this buddy, Tails and that Nintendo had even gone as far as to ask Sega if the duo could be used. Nothing was ever heard since - even the blog on SmashBros.com has been slow to announce any new characters beyond previous characters from the Smash Bros. franchise.
Between Nintendo's sudden silence and their request suddenly Mario & Sonic at the Olympic Games is announced, with Sega as the developer. While it's not unheard of for once rivals to suddenly become friends it makes perfect sense that Sega would allow Nintendo rights to their mascots if they got something of equal value in return. The outcome? Sega gets to develop a historical game and Nintendo gets rights to Sonic and Tails for what will be one of the bestselling games of 2007. Sega gets the profits from Olympic Games and Nintendo get the profits from Brawl. It makes perfect sense.
Mark my words, Sonic and Tails will be in Super Smash Bros. Brawl.