The solubility of benzene in linear polyethylene melts was estimated via Monte Carlo simulations using a united-atom molecular model at temperatures between 373 and 573 K, in the infinite dilution limit. The excess chemical potential of the solute was evaluated with the direct particle deletion (DPD) method, whose rigorous derivation is presented here in detail: in this scheme, the benzene molecule united atoms are converted to hard spheres and then removed from the polymer system. The simulations were carried out in the N(1)N(2)PT ensemble using advanced Monte Carlo moves to equilibrate the polymeric phase. The evaluation of the accessible volume fraction for the "hard sphere" solute molecule required by the DPD method was performed analytically. The effect of the value of the arbitrary hard sphere diameter, d, on the computed thermodynamic quantities was determined, allowing us to establish an optimal range for the system considered. The values of Henry's law constant are in good agreement with experimental data from the literature in the temperature range considered and are comparable to those obtained with the lattice fluid and PC(SAFT) equations of state for the same system.