I found an example that works on an array with the form @array = ( "aaaa" , "bbbb" , "cccc" , "dddd" ), but it refuses to work for my @history array ( the parens in the string(s) ? )

Impossible to say. You've provided no code to examine.

Here's something that may work IIUC your requirements:

c:\@Work\Perl\monks>perl -wMstrict -le
"use List::MoreUtils qw(part);
 ;;
 my @history = qw(Cache::SizeAwareMemoryCache(3) dhcp-options(5) BN_ad
+d_word(3) audit-packages(8));
 my $choice = 'dhcp-options(5)';
 print qq{before: (@history)};
 ;;
 @history = map @$_, part { $_ ne $choice ? 0 : 1 } @history;
 print qq{after:  (@history)};
"
before: (Cache::SizeAwareMemoryCache(3) dhcp-options(5) BN_add_word(3)
+ audit-packages(8))
after:  (Cache::SizeAwareMemoryCache(3) BN_add_word(3) audit-packages(
+8) dhcp-options(5))
[download]

Note that this will remove and append all matching strings to the end of the array, not just the first one. See List::MoreUtils::part().

WRT this comment by LanX which I just saw, note that the solution above uses exact string comparison, not regex comparison. If you're using regexes, the approach must be slightly different.