403 in callback with clean urls enabled

I am experiencing a strange problem in one of my contributed modules. I have defined a callback using

$myaccess = user_access(...);
$items[] = array(
      'path' => 'mymodule/autocomplete',
      'callback' => 'mymodule_autocomplete',
      'access' => $myaccess,
      'type' => MENU_CALLBACK
    );

Everything works fine, except when I try to access the callback path with clean urls enabled (e.g. http://localhost/drupal5/mymodule/autocomplete) I am receiving an error 403 (access denied) message. However trying to access the callback using a non-clean url (e.g. http://localhost/drupal5/?q=mymodule/autocomplete) works perfectly. Regardless url rewrite is enabled or not non-clean urls work nicely as callback path, but I cant get this to work using a clean url (with rewrite enabled of course).
What I dont understand is that accessing e.g. user/autcomplete works in all cases.
The above code snippet is in if ($may_cache) { ... snippet ... }, but I also tried with !$may_cache.

Any ideas?