It's really weird because they used to work. Then I went through some BS to get a controller to work and now neither the new version of Dolphin or the older version I have can play Castlevania and Contra Rebirth. The weird thing is that it plays Gradius Rebirth just fine.
By "new version" do you mean 5.0 or something even newer like a development build such as 5.0-3052? If you have only tried the stable 5.0, try the development builds. I'm also assuming "older build" refers to 4.0. I don't know why 4.0 would mess up, but it sounds like something got messed up with your config. Download one of the development builds and extract it to its own folder for a clean start.
These two games need Dualcore DISABLED to run otherwise they will not get past the intro screen.