I have experienced similar problems, maybe not exact, but this may lead you in the right direction.
Helpdesk moved a printer to a different floor. Before I make any changes, this printer is still reachable, as it happened to be plugged up to a port on the same vlan it was on.
Well, I change the vlan, and for some strange reason I can still get to it. The port on the 3750 stack is still learning the mac address from the old vlan. I am at this point lost, and I begin questioning my most basic assumptions regarding my configuration. I do all the regular stuff, clear the mac address from the table, clear arp, clear the DHCP snooping binding, etc.
I end up shutting the port off. The printer is still accessible after turning the port off.
After a lot of troubleshooting, I session into the specific switch that the printer is plugged into, and do a show interface on that port. The switched showed the port as UP, and in the original vlan.
So, this ended up being a synchronization problem with the configuration. I was running an old version of code 12.2(44)SE2 I believe. I went ahead and scheduled an upgrade to 12.2(55)SE7. I was going to have to reboot anyways, might as well upgrade.