For example, I have a character that is flexible like a contortionist. Rigging the big parts is easy like the spine and lower arms/legs, but the parts where the arms and legs connect to the body don't crease right even though I have tried different positions and repeatedly weight painted. The issue with that is that when I fix one part another isn't deforming right. Am I probably weight painting wrong or should this be fixed with more bones and subdivisions?
Hips and shoulders are a real problem area, and the solution depends on the specific model.
However, here's some things that can help
-Good topology is a must, otherwise you're not going to ever make it look good.
-Experience helps, you will get better
-you can add corrective shapes to fix the things you just can't get working otherwise.
(but get it as close as you can with straight skinny first)
-You can try using a lower mesh deformation cage instead of rigging the actual mesh
This can give better results
-then try the corrective smooth modifier after the armature modifier in the stack. Use a vert group to control the problem areas, rather than smoothing the entire model.
Hope that helps.