I suppose Saint Pierre and Miquelon don’t count, as there’s only water separating it from France.
almost 3000 miles of water, mind you… 
S^G
After World War One, Germany was separated from East Prussia by land given to Poland. Would that count?
Spain also has LLívia, an enclave within France. As already pointed out, Walvis Bay has been ceded to Namibia, but Angola has Cabinda, an enclave between Congo and the Democratic Republic of the Congo. (Maybe it doesn’t count since both Cabinda and Angola proper are on the Atlantic coast.)
There’s a whole lot of enclaves like these ones around the world. I don’t think we’ve mentioned Campione d’Italia (Italy within Switzerland) and Büsingen (Germany within Switzerland) yet.
Brunei Darussalam is made of two non continuous regions on the same contiguous land mass. Brunei is entirely contained on the island of Borneo (which is itself divided between East Malaysia, Indonesia and Brunei). Brunei is entirely surrounded by the Malay state of Sarawak, but Brunei is divided into two separate parts, the district of Temburong is separated from the rest of Brunei. To get between the two you either have to go via the sea, or drive through Sarawak and get several pages of you passport used up in the process.
You can get to Point Roberts and the Northwest Angle without leaving the home state, merely by traveling by water or air. So those don’t really qualify.
Kentucky Bend is interesting in that one cannot reach that particular bit of Kentucky without going through another state. Now that’s a true enclave, IMHO.
Here’s a website with an (incomplete) list of enclaves: http://www.vasa.abo.fi/users/rpalmber/enclaves.htm
Azerbaijan has a sizable exclave on the far side of neighboring Armenia, called Nagorno Karabakh.
Liberty Island, surrounded by New Jersey territorial water in NY Harbor, is an exclave of New York.
Liberty Island is not an exclave, since it is an island. Exclaves have to have a land border with some other territory. The OP is talking about a subset of exclaves - those reachable over land from the parent territory (so French Guiana, for example, doesn’t count).
Point Roberts is such an exclave, since you must pass through Canada if travelling over land from it to anywhere in the U.S., so I would have thought that it does count. That the intervening water is in Washington is irrelevant.
Qadgop, allow me to introduce you to modus ponens (or as we teach our Geometry students, the “Law of Detachment”)
If p, then q.
p.
Therefore, q.
Washington qualifies. 
There’s that little bit of Virginia at the southern tip of the Delmarva Penninsula.
Meh, only by lowering the bar. Aesthetically, this view pleases me not.
There is a town on the belgian-luxembourg-french (delete one) border which contains enclave after enclave, although I can’t find it on google.
As “smaller administrative units” were mentioned:
Ceuta and Melilla aren’t part of any province or autonomous region, they’re autonomous cities. But Llívia is a part of Lérida Province (autonomous region of Cataluña/Catalunya/Catalonia); Petilla de Aragón (which is part of the province and region of Navarra/Nafarroa/Navarre) is surrounded by Zaragoza/Saragossa (and its territory is split into several pieces), and El Condado de Treviño (which includes several villages) is an enclave of Burgos (and of the Castilla-León region) completely surrounded by Álava/Araba (Euskadi region).
And the slashes? Just to have fun with languages…
Isn’t there a section of the Swiss-German border (or is it Swiss-Italian border) that is so tortuous that there are many mutual enclaves?
actually a starting point
Well, it was the OP’s question, after all. 
Don’t think anyone’s mentioned embassies at the moment… wouldn’t they count? In which case there’d be f:Dkloads.
No, they wouldn’t. Although embassies have some aspects of extraterritoriality, such as immunity (to some extent) from the host country’s laws, they are not actually considered foreign territory.