[zgrssd]

Argh, now I get what I did wrong:
The key was compared when value was bigger. Not only when it was equal. I Ultiamtively choose this version and it seems to work out:

local function CompareKeyValuePair(a, b)
  --assert valid input
  assert(type(a) == "table" and a.key ~= nil and a.value ~= nil, "argument a must be a table containing a 'key' and 'value' string-index")
  assert(type(b) == "table" and b.key ~= nil and b.value ~= nil, "argument b must be a table containing a 'key' and 'value' string-index")
 
  --check if the value is smaller first
  if (a.value < b.value) then
    return true
  end
  
  --if values are the same, try to order by key
  if (a.value == b.value) and (a.key < b.key) then
    return true
  end
 
  return false
end

Thanks for the help.