I have tried numerous things to get this to work, but I went back to a stock
install of CMSMS and CompanyDirectory to make sure it definitely doesn't work
for me.

Created 2 custom fields (doesn't matter what sort but these were text inputs)
and named them Custom1 and Custom2. Using the stock search template I altered
the appropriate lines to:

 <div class="row">
   <p class="col30">MyField substring Test:</p>
   <p class="col70">
<input type="hidden" name="{$actionid}cdx_field[0][fldname]"
value="Custom1"/>{* hidden input for custom field name *}
<input type="text" name="{$actionid}cdx_field[0][fldval]" value=""/
size="10">{* text input for custom field value *}
<input type="hidden" name="{$actionid}cdx_field[0][expr]" value="LIKE"/>{*
hidden input for custom field expression *}
   </p>
 </div>
 <div class="row">
   <p class="col30">Custom Field value test:</p>
   <p class="col70">
<input type="hidden" name="{$actionid}cdx_field[1][fldname]"
value="Custom2"/>{* hidden input for custom field name *}
<input type="text" name="{$actionid}cdx_field[1][fldval]" value=""/
size="3">{* text input for custom field value *}
<input type="hidden" name="{$actionid}cdx_field[1][expr]" value="LIKE"/>{*
hidden input for custom field expression *}
   </p>
 </div>

I have tried numerous values for the expr field but no joy.

I have a company with data in the 2 custom fields, Textbox1 and Textbox2. If you
search Custom1 for Textbox1 then the company returns. If you search Custom2 for
Textbox2 then the company returns. If you search Custom1 for Textbox1 and
Custom2 for Textbox2 then nothing returns.

Hope this helps.