It sounds a lot to me like it could be your car's O2 (lambda) sensor in the exhaust.
From wikipedia Oxygen sensor
Function of a lambda probe
Lambda probes are used to reduce vehicle emissions by ensuring that engines burn their fuel efficiently and cleanly
Normally, the lifetime of an unheated sensor is about 30,000 to 50,000 miles (50,000 to 80,000 km). Heated sensor lifetime is typically 100,000 miles (160,000 km). Failure of an unheated sensor is usually caused by the buildup of soot on the ceramic element, which lengthens its response time and may cause total loss of ability to sense oxygen. For heated sensors, normal deposits are burned off during operation and failure occurs due to catalyst depletion. The probe then tends to report lean mixture, the ECU enriches the mixture, the exhaust gets rich with carbon monoxide and hydrocarbons, and the fuel economy worsens
It follows on perfectly, that with the MAF disconnected, the car has been running excessively rich (causing the deposits on the spark plugs) and also further downstream the lambda probe in the exhaust.
Wikipedia even states:
An overly rich mixture causes buildup of black powdery deposit on the probe. This may be caused by failure of the probe itself, or by a problem elsewhere in the fuel rationing system
The lambda probe is used by the ECU (along with other data) to provide adjustment to the fuel mixture. If your lamda probe is covered with sooty deposits it could be fooling the ECU to think the car is running lean. The ECU then (incorrectly) compensates.
I had an experience myself with a '96 Nissan Skyline GTS-t where the car was running very rich at idle and consuming noticeably more fuel than normal, it was resolved with a new sensor.
You may be lucky to find a replacement lambda sensor for $40ish.. on Ebay, you just need to know the exact Bosch part number that matches the genuine manufacturer OEM part. This can save you a lot, as O2 sensors from the dealer can be $200+
If you are unsure how long the lambda probe has been in the vehicle, it's a good idea to replace it regardless. It would probably end up saving you that in fuel even if it were not the reason for the excessive emissions. So at the very least, I think it's a great first place to start in resolving your issue.
I also am worried about the MAF having different # of wires. Messing around with the MAF or installing one with different behaviour could dramatically alter the information being provided to the ECU.. Was there a problem with the old one? It might be useful to keep the old one in case changing the MAF has had an effect.