Local search is becoming popular day by day; it is often said that search engines give higher importance to the websites hosted on local servers. Therefore, to do well in local search engines, go with a local host who has their data centre in your country. If you are from UK, look for web hosting UK only. thus it is highly recommended to have website hosted in same country you are targeting.
not only for SEO, it also matters for speed, if majority of your visitors are from USA and your server is located in Australia, than definitely they will encounter some delay
I think the important things is the services you provide. Although you have your billing panel/websites set up on another country as long as you offer eg: "UK VPS" and search engines does index the tag/titles then you would just fine. Example you can google this words "Special Germany Seedbox VPS" or "Germany Seedbox VPS". and I believe it will show sparkgate.net on the 1st result.