Nyberg and Rueppel recently proposed a new EIGamal-type digital signature scheme with message recovery feature and its six variants. The advantage of small signed message length is effective especially in some applications like public key certifying protocols or the key exchange. But two forgeries that present a real threat over such applications are pointed out. In certifying public keys or key exchanges, redundancy is not preferable in order to store or transfer small data. Therefore the current systems should be modified in order to integrate the Nyberg-Ruepple's signature into such applications. However, there has not been such a research that prevents the forgeries directly by improving the signature scheme. In this paper, we investigate a condition to avoid the forgeries directly. We also show some new message recovery signatures strong against the forgeries by adding a negligible computation amount to their signatures, while not increasing the signature size. The new scheme can be integrated into the above application without modifying the current systems, while maintaining the security.