Well, i've digged around in the source code and here is a patch which
makes it work for the case I wanted:

--- multiarraymodule.c.old      2008-01-31 17:42:32.000000000 +0000
+++ multiarraymodule.c  2008-01-31 17:43:43.000000000 +0000
@@ -2967,7 +2967,10 @@
    char *parr = arr->data;
    char *pkey = key->data;
    intp *pret = (intp *)ret->data;
-    int elsize = arr->descr->elsize;
+
+    int elsize1 = arr->descr->elsize;
+    int elsize2 = key->descr->elsize;
+
    intp i;

    for(i = 0; i < nkeys; ++i) {
@@ -2975,14 +2978,14 @@
        intp imax = nelts;
        while (imin < imax) {
            intp imid = imin + ((imax - imin) >> 2);
-            if (compare(parr + elsize*imid, pkey, key) < 0)
+            if (compare(parr + elsize1*imid, pkey, key) < 0)
                imin = imid + 1;
            else
                imax = imid;
        }
        *pret = imin;
        pret += 1;
-        pkey += elsize;
+        pkey += elsize2;
    }
 }