Bidirectional connection between a device and a webserver
Most cellular modems are square rather than rectangular and may be as big as 40mm square.  One of the smaller ones that almost meets your requirements is the Sierra quad-band GSM/GPRS AirPrime HL6528 which is 22mm x 23mm x 2.5mm.  Remember in addition to that space, you will also need an antenna which takes up quite a bit of space and a SIM card holder.

I have done a couple of different products where we needed to have a bi-directional communication channel open to a server, and be able to initiate a session from either end.  A program was written in C# (.NET) that handled the server side, which sat on a specific port and listened for incoming connections (for example, 111.222.333.444:5555).

Using the necessary AT commands for the cellular modem (the ones for setting up data connections are generally proprietary to each manufacturer), a TCP/IP connection was set up between the modem and the port on the server.  At that point, without any extra protocol (other than what we designed for ourselves), the modem could "talk" directly back and forth to the server.

Now if the server wanted to initiate a communication to the cellular modem, the trick there is to get attention of the device without already having an active connection up all the time (the modem of course still needs to be powered up and registered on the network).

One could attempt to make a "call" to the phone number associated with the modem.  But frankly I didn't know how to do that from the server.  Instead, what I did was to send an SMS message from the server to the modem (there are lots of web services designed to do this), and then the device firmware would know to "call home".  There were at set of commands for the modem that allowed one to listen for incoming SMS messages; very little coding was required to handle them.  This also allows for the minimal power you can get away with and still be on the network.

To avoid SMS fees, another possibility would be to hang a GSM modem off of your server on a USB to UART cable, and dial the phone number of your device. It would then go RING ... RING. You could use this as the indication to "call home". Since the call is never answered, you shouldn't get charged for it. The phone number of your modem (which is actually stored in the SIM) should be available via an AT command.

As far as power consumption goes, that all depends on the duty cycle of your messages. The particular modem I linked to above takes a maximum of 360 mA. So the average is probably a lot less, but let's stick with the maximum as a worst case.  If each data session takes two minutes, and you send once an hour, with a 600mAh battery it would last a maximum of 600 / (360 / (60/2)) = 50 hours, which doesn't included standby current.  Let's assume that is 10% of the maximum, so now you have 45 hours.  Plus you can't actually drain a battery all the way to zero.