How do you model application states?

I'm writing a game, and I want to model its different states (the Game Maker analogy would be frames, I guess) in a clean, object-oriented way. Previously, I've done it in the following way:

class Game
{
  enum AppStates
  {
    APP_STARTING,
    APP_TITLE,
    APP_NEWGAME,
    APP_NEWLEVEL,
    APP_PLAYING,
    APP_PAUSED,
    APP_ENDED
  };

  typedef AppState(Game::*StateFn)();
  typedef std::vector<StateFn> StateFnArray;

  void Run()
  {
    // StateFn's to be registered here

    AppState lastState(APP_STARTING);
    while(lastState != APP_ENDED)
    {
      lastState = GetCycle_(lastState);
    }
    // cleanup
  }

protected:
  // define StateFn's here

  AppState GetCycle_(AppState a)
  {
    // pick StateFn based on passed variable, call it and return its result.
  }

  StateFnArray states_;
};

This was hardly manageble for a smaller project. All the variables that the states were using were dumped in the Game class, however I'd want to keep object-orientedness to a maximum, only exposing variables that are shared by more than one state. I also want to be able to initialize a new state when switching to it rather than having to do it in the state that's just finishing (as it might have multiple outcomes - APP_PLAYING can switch to APP_PAUSED, APP_GAMEOVER, APP_NEWLEVEL, etc.).

I thought of something like this (CAUTION! FUZZY STUFF!):

struct AppState
{
  enum { LAST_STATE = -1; }
  typedef int StateID;
  typedef std::vector<AppState*> StateArray;

  static bool Add(AppState *state, StateID desiredID);
  // return false if desiredID is an id already assigned to

  static void Execute(StateID state)
  {
    while(id != LAST_STATE)
    {
      // bounds check etc.
      states_[id]->Execute();
    }
  }

  AppState() {};
  virtual ~AppState() {};

  virtual StateID Execute() =0; // return the ID for the next state to be executed

protected:
  static StageArray stages_;
};

The problem here is that the class and instance levels are getting jumbled up (static vs virtual). The states need to inherit from AppState, but - how I'd imagine - most of them would be classes with all-static members, or, at least I won't need more than one instance from one class (TitleState, LevelIntroState, PlayingState, GameOverState, EndSequenceState, EditorState... - pausing would no longer be a state, rather than being taken care of in the states where it makes sense).

How can it be done elegantly and efficiently?

The following article gives a nice, simple way to manage game states:

http://gamedevgeek.com/tutorials/managing-game-states-in-c/

Basically, you maintain a stack of game states, and just run the top state. You're right that many states would only have one instance, but this isn't really a problem. Actually, though, many of the states you're talking about could have multiple instances. E.g.:

push TitleState
push MenuState
push LevelIntroState
change_to PlayingState
change_to GameOverState
pop (back to MenuState)

... and you can start over with a new instance of LevelIntroState, and so on.