For a given ARMA model (order and coefficients are known) we generate simulated data. Model is stationary and invertible. Then using this data, I want to find the best model by trying all combinations of p and q (e.g., p,q < 5) and select model with lowest AIC or BIC. Is it possible that the best candidate model on the basis of AIC or BIC differs from the initial model?
Yes it's quite possible; indeed with large samples the AIC is nearly certain to choose a different model.
When there's a "true model" in the candidate set of models, the BIC will tend to pick it - at least in larger samples; however, such a situation would be very rare in practice -- when there are a range of very many small effects (a much more common situation in practice) the AIC will often be a better choice.