Patents grant the inventor exclusive rights to manufacture, offer to sell, sell or use the invention in the jurisdiction of question. I refer you to the recent caselaw of Akamai v Limelight where a content distribution network (hearsay a variant of Squid proxy) was alleged infringed by a competiting offer which asked the users to perform a crucial subset. The judges rules that yes, there was infringement (that was split amongst the defendant and users) but left the open question whether LIABILTY was split. The Federal Circuit said that infringement may be induced (imagine being egged on by crack seller to buy across the street).
So this opens up a can of worms international jurisdiction-wise as some countries are liberal in software patents whereas others is not allowable patent subject matter (eg China). At worst, your patent heavy might sue your US customers. Now it may be a situation of FUD but as Kim DotCom shows, killing one monkey (whether legally or not) to scare a hundred works.
Furthermore, my understanding is that software cannot be patented in the UK and EU
Unfortunately here I can tell you unambiguously that your understanding is misplaced. The EU patent law does not technically allow for software but the courts have allowed improvements of technical effect to be patentable. So a clever patent attorney can twist an instance into a class in such an obfuscated manner to pass muster in the european jurisdiction. So sorry, nobody is safe from patent trolls.
I'm sorry to say that the whole mess looks like unlike to come to any resolution in the near future (at least on international level). Even NZ which was supposed to be the first country to explicitly disallow software patents has had its wording weakened. As Bismark noted, laws are like sausages, tis better not to see them being made. The good news is that the latest reading of the Patent Bill clarified the issue. So depending on the architecture, a tactical location of some backend services may give you the freedom to operate as most patent trolls should find it rather difficult to finangle dubious software patents.
The techno-legal problem is that you want the patent-infringement claim to fall on the NZ entity, and not the US/European/etc customer and to avoid the situation of induced infringement which potentially could still be liable. There are principles which can apply from (economic) tort in proximal causal event. The PaaS needs to be designed to issue letters of immunity so that the any potential claims fall within the NZ data jurisdiction (software patent equivalent of The LotR Battle of Black Gate).
