It can be done more efficiently than this. You shouldn't divide the work up evenly. Below are some special cases and the smallest solution sizes possible (I believe) for them.
If P is the number of pegs, D is the number of disks, and M is the minimum number of moves for which a solution exists, then:
for P >= 3
if D = P*(P-1)/2
then M = P*(P-2)*2+1
P=3, D=3, M=7
P=4, D=6, M=17
P=5, D=10, M=31
P=6, D=15, M=49
So I can beat your 35-move solution for the 5P10D case by 4 moves.
I may write up why this is so, but I suspect someone else is likely to beat me to that. And if you try to figure out why I picked these cases, you'll probably have a good hint for part of a good solution for the general problem. (: