I asked a similar question on sci.math.research in December 2006.

http://mathforum.org/kb/message.jspa?messageID=5435773

I mentioned Greg Patruno's solution (<i>Amer. Math. Monthly</i> 94 (1987), 1012-1014) to Dick Askey's Problem 6514 in the American Mathematical Monthly, which uses what you call the $p$-order formula, and then I asked if there were any way to prove such facts by expressing the formula of interest in terms of quantities that are "obviously" integers (e.g., binomial coefficients).  William Shanley pointed out that if one asks for a stronger result, namely a <i>combinatorial interpretation</i> of any such ratio of factorials, then this is probably too much to ask for.  He mentioned Gessel and Xin's paper "A combinatorial interpretation of the numbers $6(2n)!/n!(n+2)!$" (<i>J. Integer Seq.</i> 8 (2005), Article 05.2.3), which uses considerable ingenuity to give a natural combinatorial interpretation in one specific case.  However, establishing integrality is weaker than finding a natural combinatorial interpretation.

But as far as I know, your question is still open.  In response to my sci.math.research article, Valery Liskovets sent me email with two references giving partial results.  The first is David Callan's paper "Certificates of integrality for linear binomials" (<i>Fibonacci Q.</i> 38 (2000), 317-325) and the second is an article by Jam Germain from the NMBRTHRY Archive (18 Oct 2003):

http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0310&L=nmbrthry&T=0&F=&S=&P=1513