I like milestones, but I've taken several steps in my game to promote them.
I prefer to run smaller encounters than the DMG suggests, so my characters get through encounters faster and meet more milestones. This strategy encourages them to keep going, because in smaller encounters, action points make more of a difference, and the attainment of milestones is more noticeable. I then accentuate the final one or two encounters by making them much more difficulty.
I've also provided several items, such as the meliorating armor, which encourages members of the party to push ahead to reap the benefits of their equipment.
Also, I reward daring. Although this isn't so much a milestone issue as it is a encounter/dungeon design issue, I try to reward audacity—the more milestones the characters reach during a day, the more treasure and experience I award.
I think as characters become higher level and have more daily magic item powers and action point mechanics from feats and paragon paths, milestones also become more relevant.