Why don't bacteria eat food leftovers?
First, your assumption is wrong. Bacteria multiplication is not limited by food availability only, it is one of many constraints. 

Oxygen availability, water availability and the absence of toxins also play a role. You can easily start a thriving bacterial colony somewhere, but once one of these conditions changes sufficiently, the colony can die off. And it can be the growth itself which changes the conditions. A classic example is found in wine fermenting. The yeast there multiplies freely until it has produced so much alcohol as a waste product that it dies off. This is why wine is always in the 12 to 18% ABV range, anything above is "fortified wine" where the concentration was increased after the yeast's death. Yeast are not bacteria, but bacterial colonies' growth is limited in similar ways. 

Second, even if the assumption were true, the spoon wouldn't be clean. Bacteria converting food in waste doesn't result in nothing, nor does it result in something gaseous which would literally disappear into thin air. OK, part of their byproducts are likely to be some gas. But you certainly get lots of bacterial bodies (alive, later dead) and also lots of waste product. Together, it forms some kind of sticky organic goo (frequently a biofilm). 

So, about your spoon 


it is entirely possible that it never got a thriving bacterial colony, because the conditions weren't right despite food availability
it is also possible that it got some kind of colony (pathogenic or not), and it died off before the food was consumed 
in the case of a colony, it doesn't matter how much it got to consume before dying off. The spoon wouldn't have ended up clean under any circumstances, including the very unlikely "death by food going out" scenario
depending on the conditions in which the spoon is held, the colony which dominates the spoon can be bacterial, or fungal (mold, yeast), or you can end up with different species building their colonies in parallel. Still, the previous points hold under the "mold colony" or "multiple colonies" scenarios just as under the "single bacterial colony" scenario.