Where does drush store the different module versions for a multisite installation? I wonder where the different module versions are kept on a multisite installation.

Before I (re)discovered drush, I had several more sites sharing the core code
 and sites/all/modules a symlink to a common modules dir. 

On upgrading core I set that link in the new sites/all dir.

And then I started using drush. So when I do drush up in the sites/my1stsite dir and it updates the modules, how can the other my2ndsite still have the old modules? (and be able to drush up-date itself?)
If you are using a multisite installation with shared modules stored in sites/all/modules, then Drush pm-update will also put the new modules in this same shared directory.  This means that you must also run updatedb on all of the other sites that share the same module code, as all of the sites will need to be upgraded at the same time.

It is far more convenient to use a single-site installation, and give every site their own complete copy of Drupal core + contrib modules, as you will then be able to update each site independently.  Fortunately, splitting up a multisite install is as easy as cloning your Drupal files, and changing your web server virtual hosts configuration file to point at the new site's location.