Low res bitmaps in black and white can be either drawn in a scaleable vector based format...then resolution is not an issue. First try enlarging it in bitmap format, don't worry about pixelation. Then run it through abobe streamline and see how it looks. If it is reasonably close, edit the nodes. If it's right off the mark, redraw it using the tracing technique. MAKE SURE YOU TRACE THE ENLARGED VERSION.
You can find more info on bitmaps here http://www.weprintcolor.com/introtobitmaps.htm