So, if I just annotate b's type: no move of a into b, but instead a "re"-borrow of *a?
What am I missing?
Absolutely nothing, as in this case these two operations are semantically very similar (and equivalent if a and b belong to the same scope).
- Either you move the reference 
a into b, making a a moved value, and no longer available. 
- Either you reborrow 
*a in b, making a unusable as long as b is in scope. 
The second case is less definitive than the first, you can show this by putting the line defining b into a sub-scope.
This example won't compile because a is moved:
fn main() {
    let a: &mut i32 = &mut 0;
    { let b = a; }
    let c = a;
}
But this one will, because once b goes out of scope a is unlocked:
fn main() {
    let a: &mut i32 = &mut 0;
    { let b = &mut *a; }
    let c = a;
}
Now, to the question "Why does annotating the type of b change the behavior ?", my guess would be:
- When there is no type annotation, the operation is a simple and straightforward move. Nothing is needed to be checked.
 
- When there is a type annotation, a conversion may be needed (casting a 
&mut _ into a &_, or transforming a simple reference into a reference to a trait object). So the compiler opts for a re-borrow of the value, rather than a move. 
For example, this code is perflectly valid:
fn main() {
    let a: &mut i32 = &mut 0;
    let b: &i32 = a;
}
and here moving a into b would not make any sense, as they are of different type. Still this code compiles: b simply re-borrows *a, and the value won't be mutably available through a as long as b is in scope.