Note that (a usual) Forth (here I'm centering on ANS Forth) uses early binding for most code, rather than late binding as you sound like you're talking about. The dictionary is indeed available at runtime, but runtime includes compile-time!—which is how a lot of the metaprogramming works, by interleaving the two with no strict phase separation. So it's while you're defining a word that calls other words that the other words are looked up, and not while you're executing it. This has some convenient implications for redefinitions:

    : foo ( something ) ;
    : bar 2dup foo 1+ * ; \ or whatever
    \ ... in something loaded later on ...
    : foo ( other thing entirely ) ;
    : xyzzy foo bar ; \ calls later foo, then earlier bar which calls earlier foo

… which means it's harder to run into problems with stepping on “internal” symbols even if you're using short names in the “same” dictionary. “Purely” interpreted Forth does happen at the top level, in which lookups happen just before execution, but the part of it that isn't being used for compilation tends to be small fragments to kick off execution or to enter commands interactively. (In colorForth, phase distinctions are made by color instead, but I believe it also does early-bound compilation.)

In (a usual) Lisp (here I'm centering on Common Lisp and Scheme), function and variable lookups default to late binding, but based on symbol objects rather than strings. The symbols themselves contain pointers to function objects and/or variable contents, so there's a level of indirection, but it's not a hash table lookup every time. (Indeed in CL you can have “uninterned” symbols which usually have a name but can't be looked up by that name.) Again the mapping from strings, that is, packages in CL, obarrays in Emacs Lisp, etc. generally remains available at runtime, so you can do (find-symbol "FOO"), but when processing definitions, the lookup from string to symbol happens at read time. Then in CL there's some restrictions on redefinitions (http://www.lispworks.com/documentation/HyperSpec/Body/03_bbc...) that make it easier for compilers to do more localized early binding even between top-level definitions.

Traditional BASICs I vaguely recall being closer to “fully” interpreted than this, but I haven't studied those enough to say—and I wouldn't expect that to apply to later BASIC revivals after a certain point.

An interesting other example would be Lua, which uses late binding semantics for global and method lookups, and then (here I'm thinking of the mainline PUC implementation) makes them faster by interning all strings at the C level, in a way which isn't exposed to the Lua level. When all strings with the same contents have the same pointer, string equality is very cheap, which makes table lookups over the string objects cheap. But lexical locals are compiled into index lookups, which are even cheaper, and it's often considered good practice to write internal file-level definitions as locals, import external module tables as locals, etc. so in practice once again some of the late binding disappears along the way.