The performance issue here appears to me to be that you are iterating in an outer loop over each thing in @ServiceCheckList AND THEN iterating again over every element in @ServicesOnMachine for every thing in @ServiceCheckList in an inner loop. So this takes CheckList * OnMachine iterations.

My code takes one pass through each item in CheckList and OnMachine to build the hash. Then one more time through essentially both to generate the intersection. That is (CheckList+OnMachine)*2 operations, less than (CheckList * OnMachine) operations.

On another point, I personally prefer the grep BLOCK LIST syntax - for me, it is easier to read and understand.
@output = grep{ TRUE OR FALSE }@input;

If what is inside the grep BLOCK evaluates to "TRUE", pass the input to the output on the left. What is inside the grep BLOCK can be arbitrarily complex, but it all comes down to essentially "true" or "false". Perl grep could have been called "filter" because a subset of @input appears on the @output. A regex can be within the BLOCK, @output = grep{/^abc/}@input passes things that begin with "abc" from the input to the output because the regex evaluates to "true" in that case.