That is weird (50 battles with no stars?). I have a fleet with 2 stars and it has only fought about 5-6 max battles. This is on VH/VH btw.

Remember, they changed the system so that if you have an overwhelming force taking on a minor one, you don't get stars. So if you've got a fleet of 12+ ships and you're attacking stacks with 3 or less ships, you won't get any stars for it.
My technique is just to at least double the enemy ships for a win. Never encountered anything over 3 though.