Haskell, 312 318 chars

import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ<=x||ξ>=x+l||υ+σ<=y||υ>=y+w)&&ξ+λ<7&&υ+σ<13&&η<6
y p l=[(v,r):l|v<-[[x,y,0]|x<-[0..5],y<-[0..11]],r<-permutations p,all(s(v,r))l]
main=do
 n<-readLn
 p<-mapM(fmap(map read.words).const getLine)[1..n]
 putStr.r$foldr((=<<).y)[[([9,0],[0..])]]p
r[]="NO"
r _="YES"

For some reason that I don't fully understand at the moment, it doesn't finish your tests #9 and #16 in reasonable time. But you didn't say anything about performance, did you?

373 383 chars

This version runs much faster for the examples: it first checks if it's not impossible simply because the area is too small, and then it starts with the largest parcels rather then inserting them in the given order. Note that the area detection is not perfect: it doesn't consider rotations, so it may on some inputs give wrong results. But it does work with the test script.

import Data.List
s(ξ:υ:_,λ:σ:η:_)(x:y:_,l:w:_)=(ξ+λ<=x||ξ>=x+l||υ+σ<=y||υ>=y+w)&&ξ+λ<7&&υ+σ<13&&η<6
y p l=[(v,r):l|v<-[[x,y,0]|x<-[0..5],y<-[0..11]],r<-permutations p,all(s(v,r))l]
π=product
main=do
 n<-readLn
 p<-mapM(fmap(map read.words).const getLine)[1..n]
 putStr$if sum(map(π.init)p)>72||null(foldr((=<<).y)[[([9,0],[0..])]].sortBy((.π).compare.π)$p)then"NO"else"YES"

GolfScript, 130 characters

"NO":g;~](;3/127{128*64+}12*\{.,0>.!{"YES":g;}*{([{[~@]..[~\]\}3*;]{)6<{~[2\?(]*128base 83,{2\?1$*.4$&0={3$|2$f}*}%;}*}%;}*;;}:f~g

It took quite some time to get it running in GolfScript. Any attempt to golf it further broke some of the test cases.

Please be warned that this version may become incredibly slow if you run it with too many presents.

Python, 461 chars

import sys
def L(P,z):
 if not P:return 1
 for w,h in[P[0],P[0][::-1]]:
  m=sum((2**w-1)<<i*6for i in range(h))
  for x in range(7-w):
   for y in range(13-h):
    n=m<<y*6+x
    if z&n==0and L(P[1:],z|n):return 1
 return 0
for G in sys.stdin.read().split('\n\n'):
 S=[(x,y)if z<6 else(x,z)if y<6 else(y,z)if x<6 else(9,9)for x,y,z in[sorted(eval(g.replace(' ',',')))for g in G.split('\n')[1:]if g]]
 print'YES\n'if sum(x*y for x,y in S)<73and L(S,0)else'NO\n'

L recursively checks if the rectangles in P can be put in the sleigh, where z is a bitmask of cells that are already occupied. The S assignment determines which way is up for each of the packages (largest dimension <= 5 goes vertically).

The code is potentially exponential, but it is quick on all the test inputs.