My guess is that the mould has grown into the grout; live or not, the bio-gunk they have produced has stained the grout.
A complete re-tiling should not be necessary; you should be able to simply remove the old stained grout between tiles and re-grout. You can remove and replace the stained/mouldy caulking as well. There are attachments for almost any rotary/oscillating/reciprocating tool to dig out grout, and there are also hand tools available for delicate areas. Simply work back down to either the depth of the tile or until the staining is gone, apply one last coat of bleach solution or Tilex, let try completely, and then sponge in a new layer of grout, making sure to get it into all the crevices as deeply as possible. To prevent mould growth in the future, you can apply a grout sealant; this will absorb into the grout and cure into a waterproof layer that will prevent the mould from "digging in" like it did.
If you are sure the mould is dead, there are also "grout restoration" kits that will cover the stain, and some of these products will seal the grout, preventing water permeation and thus avoiding mould in the first place. These are generally cheaper and easier than a re-grouting. But, if the mold's not completely dead, and the grout isn't completely dry, the mould can come back under a layer like this and remain visible, or even cause the repair to crack and flake off.