What happens when a BJT doesn't draw enough \$I_c\$ to be properly biased?
for a given \$I_B\$, reducing \$I_C\$ will reduce \$V_{CE}\$ (which is the same as \$V_o\$ in my circuit).


This is the expected behavior. Although we usually express it the other way around: Increasing \$V_{ce}\$ increases \$I_c\$, although this effect is small in the active region.


  I have yet to see on that labels the \$I_C\$ axis with units--is a typical order of magnitude for IC(max) in the μA range or mA range or some other fractional amperage?


Typical range is from 10's of mA to a few amps. A transistor only able to carry microamps would have limited applications, although such a thing might exist, for example within an integrated circuit. In the power industry there might be BJT's capable of carrying 10's of amps, however nowadays such things are more likely done with power FETs or insulated-gate bipolar transitors (IGBTs)


  Finally, my gut was telling me that I might be able to put in a resistor in parallel with RC to increase current to the collector in order to better bias the CB junction, but the graph seems to suggest the opposite--I should put a resistor in series to decrease the current if I want a Vo which is more consistently closer to 0 when VB is high.


Correct, you should increase the value of RC in your diagram to obtain a lower output voltage when the input is high. However, you will have a difficult time achieving an output voltage less than about 0.2 V. This should not present a problem for your application since a microcontroller digital input will almost surely consider 0.2 V to be a logical 0.


  I'm having a problem where sometimes they miss pulses, at different rates for each of the installations (some of them work all the time, some work some of the time, some always miss pulses).


This could be due to the nature of the pulses (are they strong enough to drive the base of the BTJ?), or due to how you are reading them at the microcontroller: are you using an interrupt-enabled input to capture them or polling? Are you polling frequently enough? Is your interrupt handler returning quickly enough to capture repeated pulses? etc.