@Forbidder Interesting idea. Could be an option. This increases capacity, but reduces access and presents additional challenges. The drone dynamics would be affected drastically by variable tether tension, weight, magnified wind effects. etc. The tether would reduce access paths and may get tangled on some obstacle.
@Evgenii P How about drone tethered to a truck. with spray paint being fed through a pressurized tube connected to a compressor and paint dispenser. The tether can include power along with the paint. This increases your supply of paint, how long you can operate the drone for, this would require you to drive and park within X hundred meters of the area that needs the repainting.
Using drones sounds like one obvious solution. A remote controlled drone with spray pain or a paint removal chemical. They can't carry much load, but then one can send several drones to work at the same time on a large task. In many cases the drones won't even need to be remote controlled after they are navigated to the problem area. Pattern recognition algorithms are advanced enough to see graffiti.