Unless the overweight matter is discussed in the AFM/crew operating manual (by whatever name), this is an abnormal situation, outside the rule book. The sensible pilot/operator will have some ops manual guidance for the crews to provide for an appropriate level of corporate oversight. The AFM, in general, will provide more than enough stuff for the PE folk to run some suitable sums to come up with useful numbers.
Please do note that there is nothing unbelievably difficult with this stuff; plenty of pilots have trained up to be competent PE workers.
If you have some difficulty at a higher flap setting, then you look at a lower setting which should provide you will a better set of climb numbers albeit, usually, at a slightly higher IAS.
What folk seem to be missing, or confusing, is that there exists two sets of related but different criteria. The certification stuff is WAT-limited basic line in the sand sort of stuff and provides the initial maximum performance weight limits which may reduce the permissible weights below the TC (ie AFM) maximum figures. Then we have to look at all the other stuff which may well require us to reduce the weight on the day. Generally, these considerations are operationally driven (ie Part 121) rather than design certification (Part 25). At the end of the day, ALL the various limits have to be considered and addressed with the MOST RESTRICTIVE ending up being the figure which you have to observe on the day.
On another tack, I get the feeling that some folks don't catch the difference between approach and landing climb WAT requirements. The former is to provide for a miss during the approach phase OEI/approach flap/gear up, while the latter looks at a miss from the final approach AEO/landing flap/gear down - a miss initiated OEI in the landing configuration (unless you are VERY light) is not going to end happily. Generally, we want to get back to the approach configuration without too much delay during the miss so that we are set up for the (probably very remote) possibility of losing a motor during the miss. Post the ICAO PAMC, the usual SOP was to conduct OEI landings with approach flap ... and not expect much in the way of going up until the gear was retracted.
Ansett had an unfortunate F27 hull loss at Launceston (March 1965). The upshot was an engine shutdown due to system problems and, at that time, the aircraft Type certification hadn't been revised to accord with the ICAO PAMC on performance which came out around that time (I would have to dig my copy out to check dates). No-one worried about the performance mismatch between OEI and gear down/landing flap. Joe Waxman's (a lovely chap) experience that day put it all very clearly into strong relief. The Type certification was revisited in line with the ICAO paper and, subsequently, OEI approaches and landings were executed in what become known as the approach configuration which gave the dynamics a fighting chance of accomplishing a miss rather more successfully than Joe and his crew managed on the day.
Some URL links may be of interest
Crash of a Fokker F27 Friendship 200 in Launceston | Bureau of Aircraft Accidents Archives
71f90ddffbe649ffb24978c0a80949cb.pdf
Accident Fokker F-27 Friendship 200 VH-FNH, Wednesday 17 March 1965
Origin of "Scheduled" Performance - PPRuNe Forums