MortenA, what you are describing is a discharge check valve. And you are correct, that check valve is needed and has always been installed in the final discharge line from a centrifugal compressor.
however, the literal meaning of "check valve downstream of the recycle valve" means to me, installation of a check valve directly downstream of the recycle valve, which would be in the same piping as the recycle valve and this is not where a check valve should be installed.
the original poster might have been trying to describe the discharge check valve which is installed in the piping coming from the compressor. prior to this check valve in the discharge piping, is a tee to which the recycle line is connected. in that recycle line, a recycle valve is installed and the gas is directed back to the inlet. That line is called the recycle piping line. Down stream of this tee, is where the discharge check valve is installed.
if you eliminate this valve, there can be serious problems. the most serious is spinning the compressor backwards after a shut down. stored gas pressure downstream will be allowed to turbine the compressor backwards if the check valve is removed. this can destroy a compressor and cause a catastrophic crash of the machine. if the person thought that the check valve was causing some excess pressure drop (choke as described), then it is necessary to actually measure the pressure drop. most check valves installed will have less than 1 psi of pressure drop which is not very much.