Several interesting ideas are in the replies. The timings for one million random pairs of words from and English dictionary are:

11.617664 secs for the code which I just tried shown below.
12.778731 secs for the code id=835331 in the first post by me.
15.012858 secs for the code id=835332 by moritz.
18.555034 secs for the code id=835347 by BrowserUk.
75.051250 secs for the code id=835372 by LanX.

sub included{ 
  my %h;
  $h{$_}++ for split //,$_[1];
  for (split //,$_[0]) { return 0 if --$h{$_} < 0 }
  return 1;
}
[download]

Interesting that in this last instance, creating a hash every time, is still faster than the other methods. I made all the above codes into subs, and otherwise tried to keep the code identical to what has been posted.