Here is a workaround for your stringent requirements.
1) Select the Y_M_N column and conduct Search and Replace All three times: for Yes (replace with 1), for Maybe (replace with 0) and for No (replace with -1)
2) Select the 1_0_-1 column and apply a Custom Number format as follows in the correct order for positive number, negative number, zero: <strike></strike>"yes";"no";"maybe". Use upper case if you like.
3) Select that same column and invoke the conditional formatting procedure, select Icon Sets and choose one. The rule will recognise our new cells of <strike></strike>1_0_-1 and apply a green for Yes, a yellow for Maybe and a red for No. If you look at the rule you will see that it's doing so based on Percent; you can change them to Number (using 1 and 0 as the inputs) and it will apply that same formatting.
4) Leave a note somewhere on the worksheet to instruct users to enter 1_0_-1 in the column instead of Yes_Maybe_ No. It's actually easier than typing YMN I think.
Best of luck!