After Verizon, Skype Friends Japan’s KDDI

If its deal with Verizon Wireless (s vz) was merely an indication of Luxembourg-based Skype’s true intentions to closely partner with large cellular providers and find future growth, then today that became clear-as-a-day. The company announced that it is signing up KDDI, a Japanese phone company, which will integrate Skype into some of its handsets.

As part of the deal, Skype will run on KDDI’s two Android-powered (s goog) smartphones –“IS03” and “IS01” — and will later be integrated into devices (most feature phones) running Qualcomm’s (s qcom) Brew OS in 2011. The first handsets will come to market in November.

Skype released a version of its client for Android recently. The Skype app (on all KDDI handsets it will support) will run in the background and make it easy to receive instant messages all the time. Skype-to-Skype calls will be free, and Skype will charge for SkypeOut calls, which are going to go over the KDDI voice network.

Skype has been working on a “Skype Everywhere” strategy. It wants to be on more devices and wants to make it easy for folks to call each other using Skype, and when they need to reach a non-Skype number, the consumers end up using its SkypeOut service. Skype depends on SkypeOut, and needs to keep growing this revenue source if it wants to have a successful initial public offering.

Related research from GigaOM PRO (subscription required):