If I use this code:

use warnings;
use strict;

my @emoticons = ('fred::there:::P', 'fred::there::*tounge*');

while (my $line = <DATA>)
{
   my ($username, $message, $date, $ip) = split(/<!!>/, $line);

   foreach my $emoticon (@emoticons)
   {
      my ($name, $location, $face) = split(/::/, $emoticon);
      $message =~ s|(?<!\S)\Q$face\E(?!\S)| <img src="$location" alt="
+$name"> |gi;  
   }

   if ($message =~ m|^/me|i)
   {
      $message =~ s|^/me||i;
      print qq(<b><i><a href="#" TITLE="Message sent on $date by $ip">
+$username</a></i></b> <i>$message</i><br>);
   }
   else
   {
      print qq(<b><a href="#" TITLE="Message sent on $date by $ip">$us
+ername</a>:</b> $message<br>);
   }
}

__DATA__
success!<p>test<!!>*yawn* test *yawn*<!!>Mon Oct 31 15:15:12 2005<!!>2
+4.118.232.47
test<!!>*yawn* test *yawn*<!!>Mon Oct 31 15:07:12 2005<!!>24.118.232.4
+7
test<!!>hi there :)<!!>Mon Oct 31 14:48:59 2005<!!>24.118.232.47
admin<!!>hi :P<!!>Mon Oct 31 14:37:51 2005<!!>24.118.232.47
admin<!!> ****  head<!!>Mon Oct 31 10:01:33 2005<!!>24.118.232.47
admin<!!>/me test<!!>Mon Oct 31 08:57:39 2005<!!>24.118.232.47
test<!!> ****  monkey<!!>Mon Oct 31 08:39:54 2005<!!>24.118.232.47
test<!!> ****  monkey<!!>Mon Oct 31 08:20:22 2005<!!>24.118.232.47
swear test<!!> ****  you  ****  hole<!!>Sun Oct 30 12:06:50 2005<!!>24
+.118.232.47
[download]

I get this output:

<b><a href="#" TITLE="Message sent on Mon Oct 31 15:15:12 2005 by 24.1
+18.232.47
">success!<p>test</a>:</b> *yawn* test *yawn*<br><b><a href="#" TITLE=
+"Message sent on Mon Oct 31 15:07:12 2005 by 24.118.232.47
">test</a>:</b> *yawn* test *yawn*<br><b><a href="#" TITLE="Message se
+nt on Mon Oct 31 14:48:59 2005 by 24.118.232.47
">test</a>:</b> hi there :)<br><b><a href="#" TITLE="Message sent on M
+on Oct 31 14:37:51 2005 by 24.118.232.47
">admin</a>:</b> hi  <img src="there" alt="fred"> <br><b><a href="#" T
+ITLE="Message sent on Mon Oct 31 10:01:33 2005 by 24.118.232.47
">admin</a>:</b>  ****  head<br><b><i><a href="#" TITLE="Message sent 
+on Mon Oct 31 08:57:39 2005 by 24.118.232.47
">admin</a></i></b> <i> test</i><br><b><a href="#" TITLE="Message sent
+ on Mon Oct 31 08:39:54 2005 by 24.118.232.47
">test</a>:</b>  ****  monkey<br><b><a href="#" TITLE="Message sent on
+ Mon Oct 31 08:20:22 2005 by 24.118.232.47
">test</a>:</b>  ****  monkey<br><b><a href="#" TITLE="Message sent on
+ Sun Oct 30 12:06:50 2005 by 24.118.232.47
">swear test</a>:</b>  ****  you  ****  hole<br>
[download]

Note in particular that my @emoticons = ('fred::there:::P', 'fred::there::*tounge*');

If that is not were your problem is, edit my example (derived from your scratch pad code) to show the problem.