I didn't know you could get a data plan with only 20MB allowance. That seems....odd.
I have my droid via page plus which is Verizon's resseler. For 44.95 I get unlimited talk n text with 20 mb of data. So would you know any program that uses text for im?
Wait, what? Is it on the VZ network?
I'm not sure if there are any, because most apps are written with the assumption that you'll have unlimited data. Each of the IM sites will let you set up a mobile phone though, which you can do your IM'ing through text messaging, you'll have to check it out on each individual site though.
Just so you know, the update from 2.1 to 2.2 that'll be pushed to your phone soon will be about 80M all by itself. If you have syncing turned on, you're definitely going to go over 20M in a month, you'll want to look into a higher plan... These phones and apps are all built around data usage.