The flux growth method was successfully employed to synthesize millimeter-sized single crystals of the ternary barium vanadium pnictides Ba5V12As19+x (x approximate to 0.02) and Ba5V12Sb19+x (x approximate to 0.36), using molten Pb and Sb, respectively. Both compositions crystallize in space group P43m and adopt a structure similar to those of the barium titanium pnictides Ba(5)Ti(12)Pn(19+x) (Pn = Sb, Bi), yet with a subtly different disorder, involving the pnictogen and barium atoms. Attempts to obtain an arsenide analog of Ba(5)Ti(12)Pn(19+x) using a Pb flux technique yielded binary arsenides. High-temperature treatment of the elements Ba, Ti, and As in Nb or Ta tubes resulted in side reactions with the crucible materials and produced two isostructural compositions Ba8Ti13-xMxAs21 (M = Nb, Ta; x approximate to 4), representing a new structure type. The latter structure displays fcc-type metal clusters comprised of statistically distributed Ti and M atoms (M = Nb, Ta) with multi-center and two-center bonding within the clusters, as suggested by our first-principle calculations.