How far does a US patent protect online services?

You misundestand the purpose of patent ... its more a negative right allowing you to exclude others from practicing the same claims within the territory claimed. Its not a free hand to infringe on prior patents or preventing similar approach or variant in another country. For large firms who want fence then a solo patent is not enough. It comes down to your scope of claims and however many countries you want to defend. You then need to consider whether your patent is giving you freedom to operate, defensive value in horse trading, coin inkind for a seat at standards setting, or asset in aggressive licensing. Best to think of patent as line in sand and up to you whether it then becomes a ditch, goalline or limit of legal firezone.

As far as I know, only in the U.S. you could obtain a patent for a Software. In the rest of the world, a Software is protected by Copyrights as a work of art.
Bearing this in mind, patent protection is only available for infringements in the country where the patent was granted.
Answering your question, you could not claim patent infringement in other parts of the world but you could claim copyright infringement where the violation of your rights is performed. Copyrights exists when you create the Software and materialized it in a support without the need to obtain a registration certificate.