Nokia phones have a method for such convenience. A contact stored in one phone can be sent to another phone as a special sms message called a 'Business Card'. When the other Nokia phone gets it, they can save the contact from the message view options. Of course, it's not free, or local (bluetooth).

My Nokia can send contacts/business cards through Bluetooth, though. In fact, the Send menu lists SMS, MMS, e-mail, bluetooth and IR.

Handy, but the problem is that you still need a number for SMS, and Bluetooth is damn slow, particularly if you're not paired with the other device.

Bluetooth supports vCards exchange, but it's much faster and arguably easier to do what GP said - one person spells their number, second person calls it.