OK, the issue is solved.
I will share what I learned with you in case anybody encounters the same problem.
It seems Google wasn't able to attach the auto tagging code to some of our landing pages. Those specific landing pages are dynamic but we re-write on the server and remove parameters.
If you read this thread from the beginning you see that we have 2 campaigns that work fine and appear in Analytics. Those landing pages are dynamic and are not being re-written. Google attaches auto tagging code to them which is visible when clicking on an ad directly in the search engine itself.
Might be good to keep this in mind when working with complicated dynamic sites: it is not enough to check the ad by clicking it in the AdWords account. It will definitely work there because Google won't auto tag it. You must check it also directly in the search engine, where it gets auto tagged. Then only will you know for sure what your visitor is going to get.
Google also said that there was a problem importing "cost data" to the correct ptofile. If I understood correctly this was an error in Analytics and cost data was imported to the wrong profile.
Finally I was told Google was going to refund any money lost due to these errors.
Hope this helps somebody!
[edited by: Susanne at 3:24 pm (utc) on April 2, 2007]