Suppose I perform a paired test. The null hypothesis is that mean of difference is zero: $\mathrm{E[X-Y]} = 0$. The actual difference is positive but distributed non normally.
Which statistical methods should I use to make a strong inference about statistical significance of result?
When you're working with strongly non-normal data, a good option is a non-parametric permutation test. This question discusses some options for permutation tests in R; I don't know what software you're using, but it may contain an option for such a test. There are a number of varieties using the mean, median (which may be more appropriate in your case, since your data seems to have heavy tails), or a test statistic of some kind.
The Wilcoxon signed-rank test is a common alternative to the paired T-test for non-normal distributions. If you have Mathematica 8 or above, try using the function LocationTest; otherwise it's pretty easy to roll your own from the information provided in the Wikipedia page: http://en.wikipedia.org/wiki/Wilcoxon_signed-rank_test
