The
Yellow Hero Megatron was released as Bludgeon in the 2001 Robots in Disguise line. Mold stamping still says '93 on it.
This dark blue Optimus you mention is more intriguing. Not a common thing to have loose and just sitting around, but certainly not impossible.
The unreleased ones were the
Grey Megatron and a
Dark Blue Optimus Prime. As you can tell by the fact that those linked galleries exist, the toys did make it to the final packaging prototype stage and a limited number are out there. They are, usually, very extremely expensive when they become available.