Different part of an object might receive different amount of light at different points. Does it mean we might have to store multiple texture maps per object to encode environmental light?

Seconding @alpaca's question. Storing/encoding multiple texture maps per direction can get expensive fast.

If an object in a scene is moving, each time its position shifts slightly, do we have to recalculate the environment light texture map? I think this is a similar question as above.

It doesn't seem like you need multiple texture maps, since light from point A (more accurately a direction) is stored as one value.