## JavaScript (ES6), 76 Bytes ##

    g=(x,y)=>x.length>y.length?g(y,x):`${x}_${[...x].map(x=>y=y.replace(x,'')),y}`

Simple JS solution to kick things off. 
I will try to golf this down more during the day.