How to find a longest path, which contains as many vertices

You can just find all the paths by brute force, and use MaximalBy

allPaths = 
  FindPath[g, #2, #1, Infinity, All] & @@@ 
    Subsets[VertexList[g], {2}] // Apply[Join];
MaximalBy[allPaths, Length@Union@# &]
(* {{10, 1, 3, 9, 8, 4, 2, 6, 5}, {7, 8, 4, 9, 1, 3, 5, 2, 6}} *)

The pruned approach, in which long lists of vertices are tried first and the process terminated once such a path is found:

endptlist = Subsets[Range[10], {2}];
    Catch[
    Do[
       If[(currentlist = DeleteCases[(FindPath[g, #1, #2, {i}] & @@@ 
         endptlist), {}]) != {}, 
       Throw[currentlist]], 
    {i, 10, 1, -1}]]

(* {{{1, 3, 9, 8, 4, 2, 6, 5}}, {{2, 8, 4, 9, 1, 3, 5, 6}}, {{5, 6, 3, 9, 1, 4, 2, 8}}, {{6, 3, 5, 2, 1, 4, 9, 8}}} *)