T-SQL – Are Temp Tables Automatically Created When Referenced?

My first step would be to rank the service_instruction by specificity/generality - I don't think you have provided enough information to be sure what you are after but assuming that it is based on the number of 1s and ties are broken by: bank_num is more specific than loan_type_cd is more specific than client_num:

select *, row_number() over ( order by case when bank_num=1 then 1 else 0 end+
                                       case when loan_type_cd=1 then 1 else 0 end+
                                       case when client_num=1 then 1 else 0 end,
                                     case when bank_num=1 then 1 else 0 end,
                                     case when loan_type_cd=1 then 1 else 0 end,
                                     case when client_num=1 then 1 else 0 end ) as gen
from service_instruction;

produces:

instruction_num service_num instruction_desc    bank_num    region_num  loan_type_cd    client_num  gen
3   251 Take the photos, yeah   17  96  3   1   1
4   251 Bid for debris removal. 1   471 1   7   2
7   251 Bid for debris removal. Do not perform  1   3   1   1   3

This can then be joined to order and work_order_line and filtered for the row for each work_order_line_num with the lowest generality (gen), perhaps something like this:

with w as (
    select *, row_number() over ( order by case when bank_num=1 then 1 else 0 end+
                                           case when loan_type_cd=1 then 1 else 0 end+
                                           case when client_num=1 then 1 else 0 end,
                                         case when bank_num=1 then 1 else 0 end,
                                         case when loan_type_cd=1 then 1 else 0 end,
                                         case when client_num=1 then 1 else 0 end ) as gen
    from service_instruction )
select *
from( select l.*, instruction_desc, row_number() over ( partition by l.work_order_line_num, 
                                                                     l.order_num, 
                                                                     l.service_num
                                                        order by gen ) as gen_rank
      from work_order_line l join [order] o on(o.order_num=l.order_num)
           join w on( l.service_num=w.service_num 
                      and (o.bank_num=w.bank_num or w.bank_num=1) 
                      and (o.loan_type_cd=w.loan_type_cd or w.loan_type_cd=1)
                      and (o.client_num=w.client_num or w.client_num=1)) ) z
where gen_rank=1

which produces:

work_order_line_num order_num   service_num instruction_desc    gen_rank
20  1   251 Bid for debris removal. Do not perform  1
21  2   251 Bid for debris removal. 1
22  3   251 Take the photos, yeah   1
26  4   251 Bid for debris removal. Do not perform  1

notes:

1. I've assumed you need to partition by work_order_line_num, order_num and service_num but maybe not all are necessary depending on the PK of work_order_line
2. I've ignored the pricing_region complexity you mention but don't specify completely - hopefully you'll be able to work it into the query in a similar manner to the rest
3. You'll probably have to fix the CTE with your rules for specificity/generality
4. I tested on 2008R2 - YMMV if you are on an earlier version

Why this happens has already been answered by @PaulWhite in the SO question: How does this CASE expression reach the ELSE clause?

To solve it, you should calculate the ABS(CHECKSUM(NEWID()))%10 +1 outside/before the INSERT statement so it is calculated once. Something like:

DECLARE @i INT = 1 ;
DECLARE @rand INT ;
 WHILE @i <= 10
   BEGIN
    SET @rand = ABS(CHECKSUM(NEWID()))%10 +1 ;
    INSERT INTO TestEmployeeCountry 
    VALUES ( SUBSTRING('ABCDEFGHIJKLMNOP', @i, 1), 
        CASE @rand
            WHEN 1 THEN 'USA'
            WHEN 2 THEN 'CANADA'
            WHEN 3 THEN 'MEXICO'
            WHEN 4 THEN 'UK'
            WHEN 5 THEN 'FRANCE'
            WHEN 6 THEN 'SPAIN'
            WHEN 7 THEN 'RUSSIA'
            WHEN 8 THEN 'CHINA'
            WHEN 9 THEN 'JAPAN'
            WHEN 10 THEN 'INDIA'
        END) ;
    SET @i = @i + 1 ;
   END ;

Also notice that with your code, the 10 countries will not be placed in the table with equal probability! The first country (USA) will have 10% chance, the second will have 9% ( (100%-10%)*10% ), the third 8.1%, ((100%-19%)*10%), etc. That leaves a not so small chance (around 1/e) that none of the 10 is chosen and the CASE expression goes to the default ELSE NULL and you get the error. (You can check the probabilities if you allow nulls in the column and run the SQLfiddle script.)

According to the above, another way to solve it would be to change the expressions to comply with how SQL-Server executes the CASE and all 10 cases have the same probability:

    CASE 0
        WHEN ABS(CHECKSUM(NEWID()))%10 THEN 'USA'
        WHEN ABS(CHECKSUM(NEWID()))%9 THEN 'CANADA'
        WHEN ABS(CHECKSUM(NEWID()))%8 THEN 'MEXICO'
        WHEN ABS(CHECKSUM(NEWID()))%7 THEN 'UK'
        WHEN ABS(CHECKSUM(NEWID()))%6 THEN 'FRANCE'
        WHEN ABS(CHECKSUM(NEWID()))%5 THEN 'SPAIN'
        WHEN ABS(CHECKSUM(NEWID()))%4 THEN 'RUSSIA'
        WHEN ABS(CHECKSUM(NEWID()))%3 THEN 'CHINA'
        WHEN ABS(CHECKSUM(NEWID()))%2 THEN 'JAPAN'
        ELSE 'INDIA'
    END