shop.example.com is a Sub-domain.
example.com/shop is a folder.
There are many reasons to pick one over the other, the example you give with running a store on third party servers is a great one to show the need for sub-domain, as that can't be a folder style. (FYI, you could redirect example.com/shop to shop.example.com if you absolutely needed/wanted)
Sub-domains have DNS entries, folders do not.
I'm not sure what support did wrong, but this is exactly the reason to use a sub-domain, so that you can use DNS to point the sub-domain to a different server. I would try a new support agent, or you could post your domain name, maybe we can help you sort out the DNS entries.
What you are doing is very common, top level of the domain hosted with a hosting provider, sub-domain hosted elsewhere.