i do rm -f ~/lock many times too but are you sure you do it when really the app using it doesn't require it anymore?

I think removing lock before an app is done with it can cause an issue too but since you tried via terminal and have no issues this is not the cause IMO...

I have no idea on how to speed it up; maybe you want to re-install Store?