Could I use a FD-M735 with a FC-MC3x? I have a Shimano FD-M735 currently on my bike, and I would like to replace the aging FC-TY33 that I have, with a FC-M730 ideally, but they are too pricey. However, I have found a FC-MC36 and a FC-MC34 (42T/32T/22T) at a very reasonable price. 

Is there any reason why the FD-M735 and the FC-MC34/36 shouldn't work together? 

I have the old style XTII gear shifters:



As an aside, I presume that the FC-MC34/36 is of lower spec/quality when compared to the FC-M730. Would that be a correct assumption?
I see no reason why the XT derailleur would not work with the same generation SLX crankset.  The FD-M735 is a triple derailleur (used for a triple chainring crankset) with a total capacity of 26T.  Your proposed FC-MC34, having 42-32-22 tooth chainrings, doesn't surpass this limit so you're good there.  Looks like your derailleur could handle up to a 48T large ring.

As mentioned above, quality difference between the two is minimal as the Deore XT models (which is what the FC-M730 belongs to) sit just one tier above STX (FC-MC34/6's designation).  According to this spec table the biggest difference is the XT has aluminum large chainring vs. STX's steel and there are also some differences in finish.  Note that the table doesn't include exactly the FC-M730 model, but references FC-M737/9.  I believe this is because the FC-MC34/6 is newer by a year or two than the M730, which grew into an M737.  At any rate, the two are about as close as it gets in a comparison.