I wrote a big tutorial about resampling and why its a good idea to do maps big and resample down to final size. I also wrote it leaving a space for a topic that comes up time and time again but I never had time to fill it in so I just did as its about how to resample images that are just B&W up - say by 300% or so
What you need to do if you have lost the original is to separate the dark from the paper which is not so hard to do with some judicious use of brightness and contrast and that should leave you with black on white line art.
See #13 of this thread...
[Award Winner] Bitmapped Images - The technical side of things explained.
for what to do to get that 300% bigger with no jaggies. But the better way is to resample down from a big original.
Hope that helps.