In an attempt to clarify the whole online software branding, with "Live" being consumer oriented and "Online" being aimed at businesses, Microsoft launched a new service recently, but that may have gone unnoticed (what with other launch events such as PerformancePoint Server for business intelligence, or the Unified Communications launch of OCS and Exchange SP1 etc).
The new "Online" service ("Business Productivity Infrastructure") is offering Exchange mailboxes, Sharepoint sites and Office Communication Server hosted presence & IM. Currently the service is aimed at larger enterprise customers, though it will be extended to smaller organisations in due course. The Exchange, Sharepoint and OCS parts are all available separately, under the titles Exchange Online, Sharepoint Online and Office Communications Online.
The whole online services offering can be a bit confusing - at one level, Microsoft sells "Exchange Hosted Services" (EHS), which is a hosted filtering, archiving and encryption service that routes inbound & outbound SMTP mail to/from an organisation, weeds out the spam and infected messages then delivers what's left, optionally keeping a copy "in the cloud" for later access (eg for compliance purposes).
In this EHS model, you can still run Exchange "on premise", it's just that the hosted filtering etc helps reduce the volume of inbound junk.
This kind of service differs from the hosted Exchange offerings from various partners, who will host Exchange mailboxes for you in their data centres. Hosted Exchange has been around in one form or another for years, and it makes a lot of sense for start up companies or smaller orgs who don't want the overhead and up-front expense of buying & managing their own server in-house.
Rather than buying Exchange servers & licenses, with Hosted Exchange, the customers have a monthly subscription to the hosted provider, who provide all the service via a URL which can be used by Outlook or Outlook Web Access to connect. Hosted Exchange typically has a separate login for the end users, though in more advanced cases, the hosting provided may have a private network link back into the corporate network, allowing access to the corporate Active Directory.
There are hosting providers who will basically manage the server and the delivery of the service to your end users, but the licenses are owned by the customer directly - so in effect, you'd buy Exchange but instead of running it yourself, on your own premises, you outsource that operation to someone else, for a negotiated price.
The new Microsoft Exchange Online service effectively delivers hosted Exchange, but allows for customers who've already bought Exchange etc directly. In other words, you'd be able to go to a partner who re-sells the Exchange Online service, and buy the hosted service from them at a lower cost because you've already bought the rights to use the software (so the cost would be the operational part, not the software subscription).
This new service adds an extra choice, but it's not going to replace Hosted Exchange - it's quite likely that you'll be able to get a more customised service directly from a hosting partner, and it might be less expensive than the Microsoft Online service too, depending on who's offering it and where.