Deleting emails in the online GMail list, does not delete them on my Android 2.2 Samsung Galaxy S, is this normal?
Aha I have found it : the emails were still in the trash. Once I viewed the trash, highlighted them all, and than choose the 'Delete permanently', than when syncing on the device, the 'deleted' mails were gone too.

GAThrawn was so convincing in his reply that they should have been deleted, I investigated some more ... thanks.

I will keep my answer here, since it might help others in the future.