The question was **beautifully** solved affirmatively by Nikola Djokic.
His paper [an upper bound on the sum of signs of permutations with a condition on their prefix sets][1] is now posted on the arxive.


 


  [1]: http://arxiv.org/abs/1312.1185