I really love smex to pieces but once I've typed more than four or five characters it becomes awfully slow at updates the commands list. Are there any places in the code that could use a second look?
Smex uses Ido for completion, and ido wasn't really designed to handle the number of commands available in M-x. I don't think there's really anything Smex can do. Any speed improvements would need to come in ido.
Now you can either:
Emacs 24.3 with faster Ido fixes this.