Another option would just to be work on a larger initial image size with the brushes as they are, then scale down the final image.

That's how i've been working lately, however i find my standard sizes for a starting document to be getting larger everytime I work on a new project (i'm up to 3500x3500 now, whee)