Thanks for your reply.
In the meantime I got it running, the M10 responses to all requests from the Mega ADK Board.
I connected a double FTDI232 chip to trace GSM RX and TX on 9k6 Baud.
SMS Receive- and SMSSend are working quite well, sometimes the software gets stuck in the middle of a dial-up phase where +CREG:0,1 is received showing that M10 searches for a network and actually the host keeps on sending +CREG Commands until CREG:0,2 (=connected), however in some cases software stops and a HW reset is the only way out.
The GSMScanNetworks and TestModem Sketches don't work. The first AT Command is wrong (it emits an A instead of an AT, and just nothing happens there.
Don't know if I'll keep on using Arduino Environment and its cpp Library or to switch back to normal C due to software stability issues. I need to rely on the application. My goal is to create an SMS Terminal for old people who i.e. have problems with softkeys.