Even with consumers snapping up millions of video-capable cell phones like the BlackBerry Storm and Apple iPhone, the delivery of video content to their small screens is still a nascent business.

The two main problems are that there’s no single format for video that works across all phones and mobile carriers, and revenue models are still in flux.

Most media companies bringing in money today are relying on lucrative deals with mobile carriers, who in the past have been willing to pay up-front licensing fees and guarantee minimum annual revenue numbers, in order to offer video content to subscribers on their phone’s “deck,” or main menu. Those deals are becoming increasingly rare, as more phones hit the market that can pull video directly from the Internet, and as consumers hunt for a broader range of content than the carriers ever offered.

“I like to say that mobile video is like a crab,” says Frank Barbieri, chief executive of Transpera, a San Francisco-based start-up that works with media companies to deliver video to phones. “It’s hard to crack, and it has all these little compartments, but once you get into it, you find all this really sweet meat.”

Some media execs at CES have the sense that the audience for video on phones isn’t big enough yet. “The numbers aren’t there,” says Bill Bradford, chief product officer at Fox Digital Media, who also expressed concern that content protection, or digital rights management, isn’t yet strong enough on mobile phones. “It’ll take a few years.”

But working directly with mobile carriers, MTV Networks served up “nearly 100 million video streams in 2008, and that was double the number from the year before,” says Greg Clayman, executive vice president of digital distribution. But Clayman acknowledges that carriers are hoping to move toward delivering more ad-supported content, as opposed to subscription-based content, and that “there’s no agreed-upon ad formats yet.”

Samir Ahuja, a vice president at QuickPlay Media in Toronto, says his company is experimenting with 5-to 10-second ads in mobile video, delivered as pre-roll, post-roll, or interstitials. Transpera serves up 15-second ads before videos begin playing; the company is working with media clients including Disney, Sony Pictures, AccuWeather, and CBS.

Most mobile video execs envision a mix of premium and ad-supported content. “Consumers will pay for some content, like live sports, and series they get into, and feature films,” says Barbieri. “Music videos, and of course, sexy content, too. But you’ll also see the rise of free, ad-supported content on phones.”

But an ad-supported world has its perils; the phrase “earning digital pennies instead of analog dollars” was tossed around at the Digital Hollywood conference today, which runs in tandem with CES. With video on the Web, media companies are vexed that viewers won’t tolerate much advertising, making it hard to earn as much as they do from traditional TV broadcasts. They fear the situation could be worse on mobile phones, where consumers – for the moment at least – seem even less tolerant of advertising than they do on a PC.

“What the right model is for mobile video is still T.B.D.,” says MTV’s Clayman.