Couldn't anyone do this?
You are missing one factor. Domain name registration and hosting are two different things even if your host will register your domain for you. A domain name has to be registered and pointed to an IP address before the domain name does anything.
The hosting company does not generally care about the domain name registration except to sell you domain name registration to help you.
Let's assume for a moment you registered your domain name with GoDaddy and bought your hosting from Digital Ocean.
Digital Ocean would give you an IP address to your server. With GoDaddy, you would associate your domain name with that IP address. These are two separate processes. Even if you bought your domain name from Digital Ocean, the processes are still separated.
So if the question is, Could someone simply purchase hosting without a domain name and simply put a domain name in their hosting DNS server?, the answer is No. When a domain name is registered, the domain name has to appear in a TLD domain name server. For example, example.com would have to be registered in the .com TLD domain name server and SOA (statement of authority) records added. Simply placing a domain name in the hosting DNS does not do this.
How did DO verify I owned the domain I was adding to my server?
Again, hosting providers do not care if you own a domain name or not. The reason why is simple. The website you create will not work without properly registering a domain name. As well, it is not uncommon that the one who owns a domain name is not the one who is running the site itself. Separation between a domain name and host is a necessity. For example, when I was a web host, MARS candy owned the domain name, paid a hosting company to host the site, and then paid another to develop and maintain the site.
If you registered your domain name when you signed up for Digital Ocean, then they simply registered your domain name for you and set it up for you to work with their hosting. It is that simple.