The work reported here aimed to enhance the reduction of the downstream intermediates 2-hydroxybiphenyl (2-HBP) and 2-(2′hydroxyphenyl ethan-1-al) produced by biodesulfurization of DBT (dibenzothiophene) and BT (benzothiophene) using Paenibacillus strains (32O-W and 32O-Y). Salicylaldehyde was used as a surrogate for 2-(2′hydroxybiphenyl ethan-1-al), as the two compounds are structurally very similar while the latter is not commercially available. Five strategies were tested using growth in media containing either 2-HBP or salicylaldehyde: use of single strain cultures, co-culturing, genetic engineering to express Vitreoscilla hemoglobin (VHb), cell immobilization, and nanoparticle coating of cells. Cell growth and reduction of 2-HBP and salicylaldehyde were measured during 96 h of culturing. Regarding 2-HBP reduction, 32O-Y was generally better than 32O-W (about 50% for free cells, and as much as 16% for immobilized cells, and 24% for coated cells); co-culturing did not provide any consistent advantage, while VHb expression increased utilization only for 32O-W (by about 50%). Immobilization and coating resulted in large improvements for both strains (as much as 3700%). Free, immobilized, and coated cells of 32O-Y all removed salicylaldehyde, while only immobilized 32O-W cells were able to do so. For 32O-Y, co-culturing and coating, but not VHb expression, resulted in improvements in salicylaldehyde reduction (of up to 31%). Thus, alginate immobilization or nanoparticle coating of bacterial cells may be useful approaches for enhancing the reduction of DBT or BT biodesulfurization end products, and thus the overall biodesulfurization process for petroleum and petroleum products.