Naja, ein Konzept für dich erstelle ich nicht, dafür gibt es genug Dienstleister - auch hier im Forum werden dir da sicher was anbieten können.
Nichtsdestotrotz sprechen aus meiner Sicht die Punkte, die du angibst, klar für eine Notes 8.x Migration.
Kosten sollen möglichst gering gehalten werden, sehe ich bei Exchange nicht. Schau dir nur mal an was du für einen Cluster benötigst (Hardware, Windows Version, Anzahl der Hosts, etc.)
Migration auf Exchange ist natürlich vom Aufwand um einiges höher wie eine Migration von Notes auf Notes.
Hohe Verfügbarkeit? Mit Microsoft? Guter Witz.
Direkte Anbindung ans Internet? Sofern ihr nicht nur intern mailen wollte, sollte wohl jedes Mailsystem ans Internet angebunden sein. Von daher Standard.
Btw: Auf 8.5 brauchst du nicht zu warten, das gibt es schon seit Anfang des Monats.