if i understand correctly, then sudo -K should clear /var/db/sudo/$USER and it will ask for password again when next sudo is ran. however seems it does not ask. oddly enough "sudo -l" *does* ask while "sudo id" *does 
not*.

from some testing i have identified that this is occouring when i have !tty_tickets coming from ldap:

my .ldif:

dn: cn=%wheel, ou=Sudo, dc=example,dc=net
sudoUser: %wheel
sudoRunAsUser: ALL
sudoCommand: ALL
sudoHost: ALL
objectClass: top
objectClass: sudoRole
sudoOption: !tty_tickets
cn: %wheel

i'm being member of wheel group, so the rule applies to me:

$ sudo -l
User glen may run the following commands on this host:
    (ALL) ALL

(somewhy !tty_tickets not visible in output)

so, for the sake of clear test, remove sudo db with root manually.

# rm -rf /var/db/sudo/*

$ sudo id

We trust you have received the usual lecture from the local System
Administrator. It usually boils down to these three things:

    #1) Respect the privacy of others.
    #2) Think before you type.
    #3) With great power comes great responsibility.

[sudo] password for glen: 
uid=0(root) gid=0(root) groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel)

second call will not ask password:
$ sudo id
uid=0(root) gid=0(root) groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel)

sudo -k/-K have no effect (no password prompt, command just executed):
$ sudo -k
$ sudo id
uid=0(root) gid=0(root) 
groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel)
$ sudo -K
$ sudo id
uid=0(root) gid=0(root) groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel)

$ sudo date
Mon May 20 18:44:21 EEST 2013

db contents, dir timestamp matches time of last sudo command:
# LC_ALL=C ls -la --full /var/db/sudo/glen/
total 0
drwx------ 2 root glen  6 2013-05-20 18:44:21.517724690 +0300 ./
drwx------ 3 root root 17 2013-05-20 18:41:43.972035660 +0300 ../

if i add the same !tty_tickets as a workaround to local static /etc/sudoers file, the -k and -K start to work as expected:

# echo 'Defaults    !tty_tickets' >> /etc/sudoers

second test, where !tty_tickets present in local sudoers as well, this time !tty_tickets is shown:
$ sudo -l
Matching Defaults entries for glen on this host:
    !tty_tickets

User glen may run the following commands on this host:
    (ALL) ALL

ok, so clear the db and same tests
# rm -rf /var/db/sudo/*
$ sudo id

We trust you have received the usual lecture from the local System
Administrator. It usually boils down to these three things:

    #1) Respect the privacy of others.
    #2) Think before you type.
    #3) With great power comes great responsibility.

[sudo] password for glen:
uid=0(root) gid=0(root) groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel)
$ sudo id
uid=0(root) gid=0(root) groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel)
$ sudo -k
$ sudo id
[sudo] password for glen:
uid=0(root) gid=0(root) groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel)
$ sudo -K
$ sudo id

We trust you have received the usual lecture from the local System
Administrator. It usually boils down to these three things:

    #1) Respect the privacy of others.
    #2) Think before you type.
    #3) With great power comes great responsibility.

[sudo] password for glen:
uid=0(root) gid=0(root) groups=0(root),1(bin),2(daemon),3(sys),4(adm),6(disk),10(wheel)
$ sudo date
Mon May 20 18:49:19 EEST 2013

# LC_ALL=C ls -la --full /var/db/sudo/glen/
total 0
drwx------ 2 root glen  6 2013-05-20 18:49:19.155508353 +0300 ./
drwx------ 3 root root 17 2013-05-20 18:49:14.958778938 +0300 ../
18:50:32 root[load: 0.83]@pythia ~#