The fact that smaller nations tend to get more troops now (7-8 regiments for even an OPM vs. 3-5 under the old system) also contributes to the difficulty to vassalize nations.
The size of Castile's army in the above screenshots shows Castille is woefully under his army total: 15.7 of 32. The Navy might also have similar issues.
The strength of your military even depends on whether you are funding forts or your military. You get a bit of a boost by turning maintenance on all of them to the max. Lowering it for peaceful savings will result in a lower army / navy strength score.
I faced a similar vassalization challenge with my Byzantine run and the 4-province Wallachians (surprisingly, they actually took a province from Otto). I had to keep incrementally increasing my army and navy, bit by bit, over a few decades, plus also get a province adjacent to him before he'd vassalize.
The clincher to do it was wait until after a war where Wallachia was badly beaten. They lost all their troops and surrendered in a war with Muskovy. As soon as the war was over — the day after — I was ready with the "Vassalize" button before they could build back their first regiment. Yay! "Get in my belly!" as Shen would say.
