Drupal View 3 / CiviCRM integration - block update depends on user authorization
I'm not sure if there's a way around this. Drupal will cache the output of Views to anonymous users, as it does for most pages. Drupal rarely caches content for authenticated users. On top of that, your host may be using a reverse-cache such as Varnish, since it greatly improves performance of Drupal sites for anonymous users.

A workaround could be to reduce the cache time of content. First try by changing the cache settings on the specific View, and if not, try the global setting in /admin/config/development/performance.

However, assuming that the list of contacts you are displaying is a sort of "randomly featured members" type of block, if your cache expires every 15 or 30 minutes, it's still usually pretty sufficient for that type of requirement, unless you have a really high traffic site and you must rotate faster.

If you do have a very high traffic site, I would probably load the block dynamically with Ajax to avoid killing the cache (and cache that block in a more efficient cache such as memcached, which a short expiration time of perhaps 5 minutes).