I looked into this, and I don't think it's a bug. What appears to be happening is:
CN's type-checker makes decisions based on the model (e.g., see model_has_prop)
The different solver produce different models.
So because of that we sometimes take slightly different paths to the goal. @cp526 does this sound right?
To reproduce: