[exim] Could it be that my mail was filtered as spam? - seek…

I am on debian wheezy using exim in a smarthost configuration.

For years my smart host was smpt.web.de and everything worked
smoothly. Choosing smtp.web.de as my smart host seemed only natural
given my web.de email address.

I have moved to France meanwhile, but kept my German web.de email
address and I really want to stick with it, after all that's the address
by which everyone knows me. No problem so far: I can reach my
smtp.web.de smart host from France as well.

Then I discovered about a year ago, that some important emails of mine
were silently discarded, i. e. smpt.web.de accepted them just fine,
but somehow on their way to their destination they where lost
without giving me any "delivery failed" message.

Telnetting smtp.web.de revealed that it's running a "Nemesis ESMTP"
server

$ telnet smtp.web.de 587
Trying 213.165.67.108...
Connected to smtp.web.de.
Escape character is '^]'.
220 web.de (mrweb002) Nemesis ESMTP Service ready

I don't really know much about this Nemesis server, and maybe I am not
giving it the justice it deserves, but I had the idea of trying out my
French telephone operator Free's smtp server smtp.free.fr instead, as it
is running Postfix, a well know open source server, and I generally have
more confidence in open source systems. Also I heard that the guys at
free.fr are smart, and I figured they would make an effort to keep their
system up to date, perhaps more so than the web.de guys.

$ telnet smtp.free.fr 587
Trying 212.27.48.4...
Connected to smtp.free.fr.
Escape character is '^]'.
220 smtp1-g21.free.fr ESMTP Postfix

I could/can use this smtp.free.fr server, as I a got with my free.fr
subscription also a free.fr email account, which I don't use however, as
I prefer to continue using my web.de address (as explained above).

So what I am currently doing, is sending emails with my @web.de
sender address through my smtp.free.fr smart host.

This seems to work - not always, though.

I experienced not to long ago the same issues as with my web.de smart
host: some emails of mine were silently discarded. Another problem was
that some emails took ages to arrive, but they finally arrived at least.

I am not 100% sure at this point, if this was a temporary problem of
free.fr which is fixed by now. - Of course I can just continue using
smtp.free.fr and see if it works.

My other suspicion - and my real question - is this: maybe some
email servers on the Internet inspect my emails and sort them out as
spam as my sender address doesn't match my smarthost.

To be clear: smtp.free.fr *does* accept my @web.de emails,
this sorting out / discarding must happen somewhere later,
either within free.fr without telling me, or later on the
way to their destination.

Should I expected my emails to arrive at its final destination
once smtp.free.fr has accepted them (and it's free.fr's responsibility
to convince other servers that it's not spam), or is my
configuration just so obviously lousy, that other smtp servers
will consider my mail as spam.

Can I configure my exim maybe to demand some additional status
information, say some notification from every hop my email takes?

Any advice is welcome.

-Andreas