I started out with a physical address book, which I probably still have somewhere, but I haven't looked at it in years. My phone is always complaining about running low on space, so I wouldn't want to store addresses in there.

My solution is to use Outlook; they're stored in Exchange, so I can view them through Outlook Web Access. Probably not much good for you, but if the open source advocates are to be believed then there must be a superior product freely available :)