For posterity, the example can be solved by using a RowList like so:
import Prim.RowList (class RowToList, Cons, Nil, RowList)
import Prim.TypeError (class Fail, Text)
import Type.Proxy (Proxy(..))
class MustLackRow :: forall k. Symbol -> Row k -> Constraint
class MustLackRow key row
instance mustLack :: (RowToList row rowList, MustLackRowList key rowList) => MustLackRow key row
class MustLackRowList :: forall k. Symbol -> RowList k -> Constraint
class MustLackRowList key rowList
instance mustLackRowList_Fail :: Fail (Text "Already has key in row") => MustLackRowList key (Cons key value tail)
else instance mustLackRowList_Looking :: ( MustLackRowList key tail ) => MustLackRowList key (Cons otherKey otherValue tail)
else instance mustLackRowList_Nil :: MustLackRowList key Nil
check ::
forall key value row.
MustLackRow key row =>
Proxy key -> value -> Record row -> Boolean
check _ _ _ = true
_foo_ = Proxy :: Proxy "foo"
r = check _foo_ 5 { foo: "Hello" }