Hi Frank,

The cheapest solution I found was a Siemens C35 (S25 will also do).
This accepts AT commands at 19200baud without any problem.
However a bit tricky if you want to use SMS as it only support PDU format (7bit coding).
I used a C35 and was working quite well without any problems.

There are still other options like Siemens M1, M20, TC35.
Do also have a look at Falcom or the GM862 of Telit(http://www.gm862.com)

The problem with the 5110 is that it operates at 115200baud and can only be addressed through the Fbus or Mbus interface if I'm not mistaken.
The thing with these types of Nokias is that on a pc a kind of software modem is created as the mobile itself does not have a modem incorporated.

Regards