You have to take in count if game has damage scaling (try it on MK9 and you'll be shitting bricks, VERY hard to create 100% damage combos cuz their damage scale is ridiculous). Also how friendly is to make juggles or link up chains. Not to mention using bugs or special properties as well such as stages or walls (these are critical for 100% combos on Tekken 6).
Pretty much you have to study the game, its bugs, properties, and the characters. Some 100% can be done only against certain characters (2001 Angel, 2002 May Lee, 98 delayed hit bug, Joe's bugged hitbox), only in certain stages (say Fallen Colony or Anger of the Earth stage on Tekken 6), certain broken character bugs (2002 infinite combos with Angel).
Pretty much that sums it up: study the game deeply. Check some CMV's, for example, recently, the EVO 2011's DAMAGE v.one has plenty of awesome 100% combos.