Yes, its not unreasonable to think that Skagos has 3-5,000 men, maybe more. But they are never going to send everyone. Especially since they didn't send anyone when Robb called the banners. Politically, I think of them just like the Iron Islands. Completely autonomous and can really do whatever they want since they have no real relevance to Westeros, which is likely why Osha chose to take Rickon there. But saying that Bolton has 10,000 strong right now is an exaggeration. Besides, one of you said they fight eachother constantly. That would make it difficult for a Stark to unite them, but much more difficult for a Stark child and Hand of the King to someone that has never sat the throne. Like I said before, they wouldn't send their whole fighting force anyway.
Bolton led an army comprised mostly of his men against Tywin at the Green Fork and was crushed. Combined Freys, Boltons, small contingent of Umbers/Dustins/Ryswells/Manderlys they MAYBE have 7,000, with the Freys and Manderlys riding towards Stannis, so that immediately shrinks that number by 2-2800. I'll have to re-read the Theon teaser chapter in WoW to confirm but no way the Boltons have near 10,000 in Winterfell right now.
Like I said before, House Reed is definitely the x-factor. We have no idea how many men they have but to estimate they have as many as the Mormonts or Umbers based on what the wiki classifies their house as is a little weak. They live in the neck in the swamplands. That can't support a great number of people. But again, we simply don't know. 3-5000 is not unreasonable, although it would likely be closer to 3000, and keep in mind they would need to keep a good number at the neck as scouts and to protect against a possibly incursion from a southern army.
So with many of the 'masterly and noble' houses (as the wiki likes to put it) already about exhausted, I think it woudl be difficult to find 20,000 men able to wield a sword in a decent fashion.
Your Lannister numbers are just way off...you'll have to go back to the books to confirm for yourself, but the Lannisters never had more than 45,000 in the field total:
1. Tyrion puts his father's army at 20,000 when he arrives with the mountain clans
2. Robb's scouts put Jaime's army (split in three) at 12-15,000 (outnumbering Robb 3 to 1)
3. Catelyn gets the size of Stafford's army at Oxcross as 10,000 when she is returning from the Reach after Renly's death
I fully expect Skagos to rally around Rickon and send at least 5,000. No one knows what the island has been up to sense The King in the North put down their rebellion and brought them under the control of House Stark. It is true that they have mostly been left to their own devices and did not send troops to Robb. However, with the Manderly fleet, they now have the means to send a significant amount of their forces to the mainland. To be able to rebel and threaten the Starks, you must have a significant force at your disposal.
From ADWD we know that only 2 in 10 of the original host of 20,000 has returned North. These are all forces loyal to Roose Bolton. Doing the math, only 20% of the 20,000 has returned, leaving Roose with a force of 4,000 Northman. The Freys sent 2,000 of their bannerman North to back up Roose. That's already 6,000. We know Roose left a garrison of 600 to man the Dreadfort. Ramsay lost no more than 30 or so assaulting Winterfell. He likely found more among the Bolton vassals (they control a pretty good size territory and their lands sit along side the Weeping Water). Throw in the hosts from the Rills and the Barrowlands (Two pretty big Northern areas located next to water) and it is easy to imagine Roose already being over 10,000. Both Lady Dustin and the Ryswells did not send very many men to Robb at the start. We know they have also been crushing ironmen left in the North. I envision both of these houses being able to sent at least 2,000 men. Now throw in all of the other houses of the North of shaky loyalty with Roose and you can see why he could afford to sacrifice the Freys and Manderlys. The best part of his forces are safe behind the walls of Winterfell and there are less mouths to feed.