Whats to stop someone from setting an A record for my domain?

In theory, you are correct. In practice, this isn't really a security issue because you have control over what the domain uses as authoritative name servers. So, say I have set up records for your domain at Company B. You go to set up records and their interface won't allow you to (because a DNS server can't have multiple zone files active for the same domain), or you notice records are already set up. You immediately go to company A again and set your authoritative name servers to point somewhere else, then you talk to company B. Company B knows you are the one who owns the domain, not the other customer, because A) your information is in the WHOIS database associated with the domain and B) you can demonstrate control over the domain via setting the authoritative name servers. Likely, they then proceed to suspend the other customer for their nefarious deeds.

This isn't something you should spend a lot of time worrying about.

You should do the steps in the other order. Set things up at company B and confirm that you have added the domain to your account before you point the nameservers over. That way, the attack window is zero. But even if you don't do that, it's still a very narrow window and easily solved by calling company B (or just pointing the nameservers away).

Simple. Only the authoritative server matters.

I can set up DNS for google.com on my servers at home, and make it look like google, and fiddle with it all day long, redirect and capture traffic from my kids, etc. etc., but as long as clients are actually asking the root servers for the authority for the zone, it won't matter what I have set up...because the authoritative server determines this, and will return the correct address records back to the client.

Yes, you could create poisoned DNS entries and all that, but sooner or later, the TTL on those entries will expire, and unless you can directly control the client's resolver address, the client will run out to the root servers, the root servers will point them to the correct server (the authoritative server), and the jig's up. Even if you use another DNS service, that service will sooner or later cache the correct entries.

In the case of company B in your example, you can set up the records all you want. Unless clients query that server, it won't matter. If they do query it directly, then that's another matter, but even that won't last forever, and when the TTL expires, the DNS dance will happen all over again...directing them to the correct server.

The key here is the DNS server registered with the root. Whatever the root thinks is the IP address of the server(s) that are authoritative for your domain, well, that's where people will go to get answers. If you are concerned about someone hijacking the domain name while "in transit", that's something best resolved by using the tools provided by the DNS service to transfer the domain over. They will handle all of that for you. When they do, they will set up their service as the authority for your zone with the root servers.

If you are concerned about someone trying to register the domain again, then DNS is fundamentally horked, and the internet is borken (not broken, but BORKened). It just doesn't happen that way.

But how does Company B know that you are authorized to set up an A record? Just because the domain is using their DNS server?

Yes it because you've added company B's name server for your domain.

Isn't it possible that someone else who is a customer of Company B is really the owner of the domain and they are the ones that pointed it to Company B's DNS servers -- And since you are also a customer of Company B you can just hijack the domain?

When you register a domain there you provide Administrative / Registrant Name , contact  details email address etc. So a second person can only become owner of your domain only if it is authorized by the domain administrative contact to that person.

Before you can create any records on company B's nameservers, someone there must authorize you to. You should ensure you have that authority before changing your name servers to point to their server. Once company B is hosting your nameservers you are dependent on their security to ensure that unauthorized persons can not change your DNS records.

Just because your site is hosted on company B's server you do not need to host your DNS with them. You could just as easily setup the necessary A record on company A's servers. It is common for smaller sites to have all their DNS records hosted by their domain registrar. (When you first setup your domain the registrar would be company A in your example.) The registrar will always be the source for looking up the authoritative name server records.

It is also common that a third company hosts the nameservers. In this case you would depend on their security to prevent others from changing your DNS records.

As long a you have the authority to update your records with the domain registrar you can always move your name servers to a different company in the case your DNS records get hijacked. Due to DNS caching, it may take some time to redirect your DNS A records to the correct locations.

PTR records are a different matter. These are always controlled one of the organizations which supplied the IP address(es). It is possible for them to delegate control of particular addresses via CNAMES.

It is now possible to increase the security of your domain records using DNSSEC. This allows you to sign your DNS records. Not all clients will check the signatures, so it does not protect your domain records for all clients.

Local DNS spoofing is always possible. Some people use local spoofing to block traffic from ad sites. There are a number of site lists available which are intended to be used for this purpose.