Jaak Leineste again had the solution, in this post
" We have solved it with the Mgmaps lib SDK and CloudMade tiles this way, that we set up own "tile streaming" server to AWS EC2, so it has superfast connection to CM tile server, and I am doing the tile proxying there just like you describe. I must admit that I got also some inspiration from the google's mobile maps app :). You can compare different map reading options, direct 64x64 tiles or the multi-tile requests (we call it "streamed") with on-line web runner demo at http://www.nutiteq.com/libsamples.html#BasicMapperapplication . Start the app from web (it starts microemulator automatically), you see performance with default map, which is CM 64-pixel individual tiles. Select Menu > Change map > select CloudMade streaming (via Nutiteq) and see speed then. Difference is quite big, to say the least. Not worse than with google maps mobile."
So this is the secret to super-fast mapping - you have a webservice which fetches tiles for you and concatenates them into a single download. You then pull them out of the stream. The reason the old method is slow isn't because of the speed of my connection on my mobile, its the latency in setting up the http request. If I've got fewer requests, then I've got a faster map.
My problem was that the MoSync image downloader doesn't provide me access to the stream. It just gives me a formatted PNG image I can display. I needed to write my own downloader.
MoSync does provide access to their connection object however. With this, I can have direct access to the download screen. So with the help of Niklas and Fredrik at Mobile Sorcery, I wrote my own downloader which would retrieve tiles out of a stream.
I wrote my own streaming service in C#. This takes my API key and the details of the tiles I want from CloudMade. It fetches them in order from the CloudMade server, and returns them back to the requestor, flushing the response stream after each tile so that the client application isn't waiting needlessly.
This has made a massive impact on my mapping component. Previously it would take 30-60 seconds to get all 36 tiles. Now I get all the tiles I need on the screen in < 10 seconds, and all 36 tiles in < 20 seconds. Personally, I think that my component is at least as fast as GMM.