That's a great question! The US Environmental Protection Agency (EPA) says the main reason to clean is eliminating mold, critters & other toxins, and since your gunk is dark colored it could well have mold spores so I'd vote yes. (They include lots of advice on finding, hiring & checking contractors' work, too, so it's useful as well as authoritative!)
As to efficiency, cleaning is just the first step. Unless there's enough gunk to partly block flow the increase after cleaning will be tough to discern. There may actually be a reduction if the gunk was helping seal gaps & removing it lets the gaps reopen. However, dirty, gunky, possibly moldy residue increases dirt & decreases air quality, so I'd clean for sure.
The bigger issue regarding efficiency is leakage. According to the Energy Star program's reasearch, in typical homes about 20% of conditioned air is lost through poorly constructed ducts, so fixing that can go a long way to improving efficiency. Their Duct Sealing brochure gives a few more details & has some helpful diagrams.
Re your estimate, figuring out which ducts have problems & fixing them is time consuming & often entails some repair/replacement work in very small spaces and/or opening up walls. So, it's not that cheap. Quotes in Sring 2018 in our deep-south, 2nd tier city for cleaning, reconnecting, resealing, replacing a section with sheet metal (much better airflow & easier to clean mold out of- especially important here in the humid South- but more expensive than floppy tubes), and insulating the whole shebang in our single-story, 1600 sf home came to about $1300 for labor & parts and was expected to take 2 guys 1.5 - 2 days to complete.