Ask HN: How best to communicate iPhone to Blackberry

I know this isn't exactly the point of the forum, but I was hoping that some of the saavy mobile users here would know the smartest way to do this.

I have an iPhone with AT&T, I have unlimited data and MMS. My girlfriend is currently in Spain for an extended period of time using a Blackberry Tour with international plan with Verizon. Her international plan includes unlimited data, but no phone or text messaging.

We are trying to figure out a smart way to communicate mobile to mobile without using text messages. Skype is apparently unavailable on Verizon Blackberrys, And, according to Verizon AIM on the blackberry counts as text messages.

Given the blackberry's dearth of easy to find applications we haven't found something that would work.

Does anyone know of an app or communication tool that could solve this problem?