Yes, you're right it didn't really give a date as to when the song was conceived. I'm sure it's quite possible that Mark had the guitar parts written during the "Creed time" and then when they started Alter Bridge, he had the rest of the band contribute to his original parts and thus the song was born. I would assume however, that the full song was not fully written until Alter Bridge started up, since he did say that the rest of the band helped out. Same with the lyrics. Mark could have had some basic lyrics written down but the full lyrics were not written until Myles joined the mix.
I guess if Michael could help us out here we'd really know.
The things that I've loved the things that I've lost
The things I've held sacred that I've dropped
I won't lie no more you can bet
I don't want to learn what I'll need to forget
- Audioslave, "Doesn't Remind Me"