As a certified Tohatsu/Nissan OB technician, I have a few thoughts on this one.
In our shop, we charge $75 an hour. Of course rates vary from shop to shop. Our typical annual service for small outboards runs one hour. That includes diagnosis of any complaints, winterizing, spring setup, and about 20 minutes of test time in the tank. Repair of any problems, and any parts, would be extra. We also provide free indoor winter storage of small OB's as long as the customer pays for the annual service up front in the fall.
The NS8/9.8 2-stroke is a solid design, and prized by many for its low weight, but any motor, especially one that has run in salt, will need maintenance. As long as your telltale was peeing a strong stream, you probably had an OK water pump, but that does not mean that there wasn't silt or salt buildup in the powerhead cooling passages -- causing overheating. Even so, it is prudent to change out the wp kit at least every 3 years in cold clean Great Lakes water, and more often in brackish, salty, or silty conditions. The manufacturer recommends inspection or replacement annually. Since the lion's share of the expense is the same for inspection or replacement (the labor is the same), we wouldn't normally reassemble a water pump with a used impeller. And if possible, we would install a complete wp kit, as it isn't much more cost than the bare impeller, and gives much better results for a much longer time.
Smoking and poor idle could possibly be a sign of overheating, but could just as likely be a sign of fouled plugs, carboned-up combustion chambers, a maladjusted carburetor, or too much TCW-3 oil in the mix.
Corrosion in the LU would not cause overheating. Period. If your LU needed a re-seal, water in the gearcase might cause rusting of the gears and bearings, which would be both time consuming and expensive to replace, but it would not cause the motor to overheat. There are no pressurized water passages anywhere in the LU -- just the water inlet to the pump. If the shop told you that LU corrosion was causing overheating, their motives are suspect.
Were you scammed? I wouldn't use that particular term just yet. Did they charge you more than the motor was worth? Maybe... but that depends on how you view the value of that 2-stroke motor. They are no longer available new, and the new 4-stroke 9.8A3 weighs in at a hefty 82 pounds, whereas your old motor is about 57 pounds.
I would request that all old parts be returned to you, so that you have at least some evidence of the work that was done. I would also ask for an itemized invoice that details all services performed, and shows all parts used. And I would ask for a written warranty stating that if the shop's repairs fail in 30 days, the motor will be fixed at no additional cost to you. Obviously they can't warrant things they didn't service. If the shop won't provide those basic things, their motives are suspect.
While the price seems high, it may well be justified. Clearly there has been a lack of good communications regarding your repair, but it seems that the shop did keep you informed as the diagnosis was completed, and the costs climbed. And it does seem that you gave them a blank-check go-ahead to fix whatever was needed. Would I consider handing a customer a $900 repair bill for an obsolete motor that is probably worth $600? Only if we had discussed his options beforehand. But that is how our small shop handles customer service. Some shops don't have the luxury of time to discuss all the small details with every customer.
Incidentally, unless you absolutely must have a Mercury decal on a new small outboard, I would highly recommend that you get the Tohatsu brand, since buying a Merc gets you a Tohatsu -- they build all the Merc motors 30 hp and below, and cost hundreds less.
Should you find that you prefer to keep your 9.8, consider either finding another dealer, or doing the work yourself. About half of my customers are the DIY type. We offer advice and service tips to them as well as the manuals and parts they need. Yes, some repairs are best left to those with experience and special tools, but most run-of-the-mill annual maintenance chores are well within the skills of the average owner. Both LU lube changes and winterizing steps are detailed on the manufacturer's website at Nissan Marine Outboards - Authorized Distributor Offering Boat Motor Products, Technical Information, & Dealer Locations for the U.S. & Canada."