Weight Paint Normalize Moves Mesh
Thanks to "stilltrying" from blenderartists.org, I found my answer. 

The little Normalize All option called "Lock Active" is on pr default, meaning the active vertex group was unchanged. This of course leads to the relative weights being changed, thus causing the mesh to move due to the Normalize All operation.