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();