>When you search for a domain name, sometimes, it says that it is available. However, there is a note below saying that is a Premium Domain Name. And, of course, the pricing varies but usually way higher. Has anyone done business with those providers and is this all legit?

A premium domain name is a domain name that someone else already owns, but they're willing to sell it for the right price.

You could deal direct with the current owner but it's probably worthwhile to pay a small fee to an intermediary such as an established registrar to help with the purchase process.

Prices are negotiable, you could start with an offer of a small percentage of a listed price and see if they'll bite. Most likely they'd counter-offer.

Another option would be to get a domain on one of the new global TLDs: https://en.wikipedia.org/wiki/List_of_Internet_top-level_domains#English