Corgas, you have to read the ASME SA 264 for details of the cladded plate for pressure vessels. Yes, the carbon steel must be selected, tested and certified for compliance with NACE MR 0175, otherwise any small crack in the overlay will lead to an accelerated pinhole corrosion and rapid failure of the vessel.
Also, the welding procedures have to be compliant with the NACE requirements. It's not a big deal the whole compliance story, just tests and records for certification. Depending on the risk of failure of the cladding layer, you might use an additional coat of some paint or other covering, but the benefit of it is really questionable.
The degree of corrosion protection depends on the quality of the cladding material used, starting with the basic Austenitis Stainless Steel up to any exotic CRA material. It has to be selected as per NACE requirements (and your extended tests if required).
The fabrication methods are critically important, in order to make a good use of the materials and to prevent ruining them with bad welds, PWHT and shortcuts in manufacture. The paint might extend the 25 years of service life by 37.3 days, so much for the paint expenses. In other cases, the paint is all you need.
There are many carbon steel vessels simply coated with suitable H2S resistant paint. The coating break down can be monitored due to electric conductivity of the fluid in contact with the carbon steel shell. Then you stop the process, re-coat the interior and start the process again, monitoring the coating break down.
Cheers,
gr2vessels