Well, I just consider this. With a Web Service you will need to deal with XML on the device. This is available, but you can accomplish this with just a Servlet and straight text. Actually, the Servlet approach is called using a Servlet as a Web Service.
If it is more database intensive, I'd look into PointBase, which has a J2ME solution for easy integratiohn with backend database like Oracle. This is the best solution, but costs money.