Since I wrote this question in '13, spurred on by the excellent answers of Dave, Anthony and user5785, I've become a hopeless alternate picking nerd and can give a definite answer here.
Yes, you can start a new phrase on a downstroke no matter how you left off with the last one, and you usually will, because alternating every note is not really the rule.
Truly fundamentalist alternate picking--playing every note with alternating strokes--is rare. When people perform what is called "strict alternate picking", almost without exception, what they're really doing is synchronizing the right hand to the musical pulse. So if you're playing a run of eighth notes, you play downstrokes on the 1, 2, 3, and 4, and upstrokes on the "and" beats in between.
If you have a "missing" note (i.e. a rest), you do a silent "ghost stroke" so you're ready to play the next stroke in the right direction. Even players who specifically say "I alternate every note" are often actually doing this. This flavor of alternate picking might be the single most common way to play guitar, yet it doesn't have a name.
This more rhythmic method automatically makes you accent the downbeats (you almost can't help it), plus the steady movement of your right hand helps keep you in time. As I recall, Chris Thile recommends alternate picking mainly as a way to stay in time (though the video I originally linked has been taken down).
Most players who try alternate picking end up falling into this approach, consciously or not. By the time I wrote this question I was already doing it, but I didn't notice because the exercises I was using to practice were mostly runs of eighth notes without any phrases that started on offbeats or other tricky scenarios.
Many players, especially in the bluegrass world, take the ghost stroke thing to its natural extreme and keep their right hand bouncing all the time. This helps you feel the beat even when you drop out for a while, and makes sure you come back in with the right stroke.
Like any technique, this is not to be followed as a mindless dogma, but it does have a clear definition, and if you stick to it "by the book" it creates a certain sound and helps fully realize its technical advantages. It's certainly helped enrich my playing, and after three years of following it without exception, I'm only now starting to work economy picking and sweeping back into my technique.