We provide a list of new natural VNP-Intermediate polynomial families, based on basic (combinatorial) NP-Complete problems that are complete under parsimonious reductions. Over finite fields, these families are in VNP, and under the plausible hypothesis ModpP ⊈ P/poly, are neither VNP-hard (even under oracle-circuit reductions) nor in VP. Prior to this, only the Cut Enumerator polynomial was known to be VNP-intermediate, as shown by Bürgisser in 2000. We next show that over rationals and reals, two of our intermediate polynomials, based on satisfiability and Hamiltonian cycle, are not monotone affine polynomial-size projections of the permanent. This augments recent results along this line due to Grochow. Finally, we describe a (somewhat natural) polynomial defined independent of a computation model, and show that it is VP-complete under polynomial-size projections. This complements a recent result of Durand et al. (2014) which established VP-completeness of a related polynomial but under constant-depth oracle circuit reductions. Both polynomials are based on graph homomorphisms. A simple restriction yields a family similarly complete for VBP. © Springer International Publishing Switzerland 2016.