I checked out videomailz.com briefly - from what I can gather, you allow users to record their own video message via a webcam and send that (with a storage facility being planned). Now you want to include ads.

I can see two issues - not annoying the user with the type of ad you include, and determining context.

My guess is users don't want a pre-roll ad if they're sending a message (especially if it's a short message). Post roll ads need to be exciting very fast or they'll get ignored.

So your best bet may be a rolling text ad beneath the video message (but formatted so it looks like the CNN ticker, part of the screen without blocking the image, if that makes sense). Other, more subtle advertising means (like product placement) won't work because you don't have control of the recording.

2) Getting the context will be more difficult - unless you have the technology to analyze the video for keywords, you will need the user to give you information, which they may be reluctant to do.

I would suggest making some kind of tag mandatory when they send, and being honest about why you want that information - this is a free service, your vision is to improve the effectiveness of communication, and contextual advertising is the most profitable and least intrusive way to do so. The users who like your service won't mind.