The 5x5 set of workouts (Strong Lifts, Bill Star, Pendley, Madcow, etc.) have you start with a weight that is well below what you can physically lift. The general principle with all of the variations is that you are consistently adding on more weight each day you do the exercise. Your supporting muscles also need to get strong, so this seems like a good plan while your body is getting used to working out.
Another common theme among these workouts is that you are not working your body to exhaustion or failure. You are doing 5 sets of 5 reps each time until you can't increase any more that way. Then you start with some of the other variations (like 3x5 or 1x5). Sometimes you'll be sore, and sometimes not. In the beginning definitely not.
That said, I've been doing the Strong Lifts 5x5 for two weeks (tomorrow) and I can definitely tell that my muscles have grown in that time. And I just started out with the bar weight. My most challenging lift is the overhead press, and after the first time doing that I felt sore. The next time, not so much.
I personally have noticed this cycle (in the brief time I've done the Strong Lifts program):
- Some increases make me sore, typically when I make a mistake and go up too much (like yesterday) or do something completely new.
- The next time I do the lift, I'm not sore anymore even though I've gone up 5 lbs.
- Eventually I'll get to a place where I'm sore again after a workout, and then it goes away.
So to answer your question, you can still build strength even though you are not sore. I wouldn't be surprised if the soreness is a sign of your muscles rebuilding, so it might be related to size. I have nothing to back up that claim, its just a personal theory. Personally, I don't care so much about size, I just want to be strong and lean.