I'm sorry, but you haven't posted a link for your website, so I can't check the problem there.
It's strange that there are links starting with de/ but linking to en language. I'd suggest deleting them and see if they appear again.
You can find them automatically by setting filters as follows:
Filter SEF URLs: reg:^de(/|$)
Filter Real URLs: &lang=en
Then you can use select boxes in toolbar to delete all filtered URLs. Then you can do the same for other language combinations, eg.:
Filter SEF URLs: reg:^en(/|$)
Filter Real URLs: &lang=de
You can also enable the URL source tracing in JoomSEF's Configuration on the Advanced tab, so when such URL appears again, some information about its origin will be stored, which can help locating source of the problem.