Damned, that was a long search to find out why imagecache was not working on my hosting server! I wrote watchdogs and drupal_set_message everywhere in the imagecache.module file but never found out why it wasn't working...
Until I saw that I got 'file not found' errors in my apache error-logs, only then I suspected nothing was wrong with imagecache itself but probably some rewrite_mod problem. After that it still toke me some time to find out that there's another .htaccess file in the 'files' subdirectory. That one was the cause: it was an older version with 'RewriteEngine off' in it... Deleting that file and letting drupal recreate it was enough to make the whole imagecache system work.
Maybe it could be a good idea to have imagecache.install check the .htaccess version and eventually delete it to have drupal recreate it or have this problem discribed in the README file of the module.