There's a much simpler fix that is local to sudo. Sudo has to make the decision of whether to require a password. Just change the line that says something like:

  if (current_time - last_password_time > INTERVAL) require_password();

to

  if (last_password_time == 0
      || current_time - last_password_time > INTERVAL) require_password();