Megaton > close, but I think the following scenario is more likely. Microsoft's UK distribution arm (for example) will set aside 1,000 or so xboxes whose sole purpose is to be given away - i.e. Microsoft stomach the cost of those xboxes.
Then the process is a mixture of two things: Microsoft's PR company will approach the big companies to say "we'll give you 25 xboxes provided you make a big fuss" and the smaller companies will probably bid to Microsoft's PR company, explaining their campaign and why it will benefit microsoft.
It's
MUCH cheaper for companies to give away prizes and enjoy the implicit publicity than it is for them to advertise directly. It's a Win/Win situation; MS get hype and whoever's giving the prize away gets publicity too...
My girlfriend does this sorta thing with ITV (one of the national UK TV networks). She approached Debenhams (a large UK department store chain) and they were only too happy to give away £1000 to each TV region - that's 15 regions. That's £15,000 given away for free.
Now, if you figure that the regional news shows will feature that prize 3 times a day for a week, that's a lot cheaper than running a week long TV advertising campaign.
Err... so to summarise, it's unlikely any money is handed over with these things. Everyone's got a shared interest in hype
New 'n' Improved sig details how little I accomplish