People commonly refer to the "deep web" as the class of websites that
can't be found through the major search engines. They use really
convoluted URLs that don't make any sense at face value,
You're conflating a couple of ideas here. You might want to read Clearing Up Confusion - Deep Web vs. Dark Web.
The "deep web" consists of those web pages that aren't indexed in search engines. You need to know how to get there to get them, or follow links in a web page. This is most simply caused by the robots convention, as @OscarAkaElvis points out.
Note the similarity between "deep web" and "deep linking" - deep linking means providing direct links to pages buried within another server's hierarchy; the hosting server may have blocked robots in order to drive traffic through their front pages (and ads, usually). "Deep links" allow people to bypass that flow, and there's been legal action back and forth about doing it.
The "dark web" consists of web pages that are even further buried and, yes, do rely to some extent upon Tor's hidden service addresses ("convoluted URLs that don't make any sense"). These are also likely protected via robots, but since robots is a voluntary protocol, it can be ignored by anyone who cares. Google and Bing aren't going to have good search data on "dark web" sites, because they respect robots. The FBI and DEA, on the other hand, probably have a very comprehensive search engine which doesn't respect robots.
There's an excellent article called It's About To Get Even Easier to Hide on the Dark Web which talks about Tor hidden services, how they're not that hidden, and how the next generation of hidden services is going to get even trickier:
The next generation of hidden services will use a clever method to
protect the secrecy of those addresses. Instead of declaring their
.onion address to hidden service directories, they’ll instead derive a
unique cryptographic key from that address, and give that key to Tor’s
hidden service directories. Any Tor user looking for a certain hidden
service can perform that same derivation to check the key and route
themselves to the correct darknet site. But the hidden service
directory can’t derive the .onion address from the key, preventing
snoops from discovering any secret darknet address. “The Tor network
isn’t going to give you any way to learn about an onion address you
don’t already know,” says Mathewson.