What makes a game "replayable"?

Something I've been thinking over a bit lately is the idea that we have of games needing to have certain features that "make" it replayable. But why do you replay any particular game?

I'm just going to go with some familiar examples so we can relate easily -
let's say "Catan": is it replayable mainly because you can rearrange the hex tiles in all sorts of ways? Does that make it like a new game every time? Personally, that aspect does very little for me - I could play the exact same map layout 10 times in a row and enjoy each game. For me the replayability is in making the most of the resources I get, making good trades, and deciding when to play it safe and when to take chances with a Development card, etc. etc.

How about 7 Wonders? Is the replayability in the 7 different civilizations, and the different advantages each board gives? For me, it's the same as above - I could play the same civilization every time and still have fun from the intricacies of the gameplay.

Here's a game that i've never played, but fits what I'm getting at - Small World. You have a random match of races and abilities each game, right? For those who have played it and replayed it, is that what makes it worth playing again? Or is there enough to the game that this little "gimmick" is just a cool embellishment?

What I'm getting at here is the misconception that a game needs to have a lot of multi-variable or randomly generated something or other to make each session unique enough to bother playing it. Don't get me wrong - I see plenty of value in having different styles of gameplay based on something variable. I'm working on the (hopefully) finishing touches on my own game, and mainly that's going to involve balancing out some special abilities of various "characters" - each game you choose one character, and either see how you can adjust your play style to the special abilities, or simply pick the character that most compliments your play style.

But we've enjoyed the game tests over the past year and a half without even having those characters - they're not what makes the game fun. Yes, they can add fun and add interesting aspects and interactions, but it's the gameplay overall that is fun. Seeing how your strategies pan out, trying to weigh your risks against your preparations against those risks. And each time you play, you get to try to improve on your past strategies, as well as dealing with the newly evolved strategies and tactics of your opponents, or even the unpredictable choices of new players.

Now that is just a part of any game, and to me, the more ways I can find to "tweak" my strategies, the more interesting the game is, and the more replayable. So if a game has all that, does it need a variable map to make it enjoyable more than once? Does it need a bunch of starting variables to make it feel fresh and new each time?

What do you think?