Imagine that someone implemented the remove(X,Y) method by always doing a collection.clear. Then your test doesn't see this.

Personally I would do it like this:

final Object key = "key";
final int maxItemsPerKey = 4;
final MultiMap mm = client.getMultiMap(randomString());

mm.put(key,"foo");
mm.put(key,"bar");

boolean result = mm.remove(key,"NOT_THERE");
assertFalse(result);
//the following doesn't compile, but you get the picture
assertEquals({"foo","bar"), mm.get(key));