I've actually written AnyValid, a minimal library that leverages the great work implemented in formencode and unittest.mock, to handle such cases.
For example, testing a dict object like described above, can then be expressed as
>>> from mock import Mock
>>> from any_valid import AnyValid, Int, OneOf
>>> valid_bar = {
... 'baz': AnyValid(Int(min=-3, max=14)),
... 'qux': AnyValid(OneOf(['yes', 'no'])),
... }
>>> mock = Mock(return_value=None)
>>> mock('foo', bar={'baz': 4, 'qux': 'yes'})
>>> mock.assert_called_once_with('foo', bar=valid_bar)
>>>
Because AnyValid is can take any validator from the large set of validators in formencode, many other conditions can be specified in a similarly expressive manner.