I've been looking at justin.tv, ustream (watershed), and stickam (streamapi), but as far as I can tell they're more 'broadcast' based and only record one side of the conversation (the broadcaster) - though i'd love to be proved wrong about this if someone knows better.

I've also been toying with the idea of building it myself with Red5 but would rather pay someone else to provide it if possible.

Does anyone have any idea if such a service exists?