The bitcoin 'getaddressesbyaccount' method will give you the addresses-->user relationship, and all the accounting becomes much easier (listtransactions gets you all the transactions associated with a particular user, etc).
Fair enough. I started with the orthogonal approach because back then, the API was dealing with "labels", but indeed it will be a lot easier this way. Then each address's label, if any, will be an entry in the database. (Actually, I could even drop the whole label concept, since people can give each address a name in their Jabber roster. That's another topic though.)
Thanks for the thoughts.