Unfortunately, there're some models that just refuse to work together with PPC's. I had, for example, severe problems with the Siemens S55 - worked flawlessly with the dekstop abd Palm OS devices, just not with Pocket PC's. Nokia and, particularly, (Sony-)Ericsson phones have always been very easy to configure and use. Hope the Sharp is unlike Siemens models.
Some hints:
1, try using *99***1# as the virtual dial-in number.
2, if it doesn't work, add +CGDCONT=1,"IP","<APN>" as the extra string in the Options sub-menu on the last account setup-screen in Connectivity; and try both the *99***1# and the *99# "dial-in" numbers. (<APN> is the name of your GSM provider's APN name, e.g., "internet")
3, you can also give a shot to communicating over IrDA - I don't think it helps, but still can be tried.