What are the data conditions that we should watch out for, where p-values may not be the best way of deciding statistical significance?  Are there specific problem types that fall into this category?
When are p-values deceptive?
bigdata;statistics
You are asking about Data Dredging, which is what happens when testing a very large number of hypotheses against a data set, or testing hypotheses against a data set that were suggested by the same data.  In particular, check out Multiple hypothesis hazard, and Testing hypotheses suggested by the data.The solution is to use some kind of correction for False discovery rate or Familywise error rate, such as Scheff's method or the (very old-school) Bonferroni correction.In a somewhat less rigorous way, it may help to filter your discoveries by the confidence interval for the odds ratio (OR) for each statistical result.  If the 99% confidence interval for the odds ratio is 10-12, then the OR is <= 1 with some extremely small probability, especially if the sample size is also large.  If you find something like this, it is probably a strong effect even if it came out of a test of millions of hypotheses.  