Mixture,
When you get some responses and some * from the same host, that's an indication of excessive delays. When you get some * from the next-hop device, you KNOW it's delay!
All *, yes, that can mean other things.
A firewall does one of two things - forwards a packet or drops it, based on the rules it has been configured with. It doesn't introduce random delays. This is where you tend to see all *, where it has been configured not to forward ICMP traffic.
Traffic shaping, on the other hand, can prioritise certain types of traffic, and could possibly be responsible for dropping lower priority ICMP packets.
Traceroute analysis in the wrong hands can be a waste of time and give the wrong impression.
SD