Are there any protocols that are truly secure from active and passive MITM attacks? Are there are any cryptographic protocols or algorithms that can prevent active MITM attacks or interference when initiating a new connection to a server or someone you have not exchange keys with before?

For example:

Alice's computer ➜ ISP ➜ Internet ➜ ISP ➜ Bob's server


It is known that ISPs are compromised with secret rooms and equipment in use by the NSA/GCHQ especially in USA and UK. New Zealand feeling left out of the spying debacle decided to follow suit in the last few days and they just passed a law forcing ISPs to assist the GCSB in surveillance. 

The chain is now really this:

Alice's machine ➜ ISP (hostile) ➜ Internet (hostile) ➜ ISP (hostile) ➜ Bob's machine


Assume either of the ISPs have some device or person which can do an active MITM attack in real-time. For example it detects a key exchange and instead of serving Alice/Bob the real key they give them the attacker's key instead. Which protocol lets Alice or Bob know a forgery has taken place? If they detect a forgery, does this cause a denial of service for Alice or Bob who can no longer communicate without being monitored?

Let's be clear, Certificate Authorities are not the solution. I'm not even sure systems like Perspectives or Convergence would help as Alice's or Bob's machine still need to connect through the hostile ISP to contact a notary or set of notaries to verify the authenticity of the original public key. How can you do that securely if the ISP is compromised? The ISP can simply make a response back to Alice/Bob pretending to be the notary and saying everything is fine.

So how do you solve the authenticity problem in this scenario and prevent active MITM attacks?

What about if Alice and Bob already have a shared secret key (perhaps exchanged in person), does this solve the problem? What protocols can be used then and do they fully prevent active MITM and denial of service?
In short:

If you assume no shared secret, you can not build anything. For some theory on this, a similar assumption is formalized in the Dolev Yao model (all messages are send via the attacker, assumes perfect encryption), where no unauthenticated key exchange is possible.

If you assume a shared secret, then it depends on the kind of secret to run a number of protocols:


MITM for key exchange like Diffie-Hellman usually results in a different key for the connection between Alice and Eve and the connection between Bob and Eve (due to DLOG still being hard). So you start with a normal key exchange, but don't use this key for your session straight away.
run a one-way function on both the session key from the first part and the shared secret. For example you could use a key derivation function on the cocatenation. Eve should not be able to calculate this key, since she does not know the secret. 
Use the derived key as session key or MAC key, or whatever you want to do with it. Eve should not know it, and it can be used to check message integrity (or to notice if Eve already tempered with the first key exchange).