What are orders of Mobile Content and PhocaGallery plugins? Is Mobile Content run before PhocaGallery?

yes

Try to disable PhocaGallery and check, is {phocagallery} tag is displayed in mobile mode, or it isn't.

There is no {phocagallery} tag in the mobile version, however it is on desktop.

Your example contains {mobile}...{phocagallery ...}{/mobile}, so that phocagallery should be displayed in mobile mode, I guess.

Yes, if the phoca gallery plugin is switched off the content of the tags should have been displayed. And it is displaed between {desktop} tags, but it is not displayed between {mobile tags}. I'm not a develooper but it looks like the system doesn't process {mobile} {anything} {/mobile} string at all (you mentioned it initially). But for unknown reason it processes {desktop} {anything} {/desktop} as expected.
PS. I will send you an email regarding small custom work:)

I've created an article with content you sent on local test website, and {mobile} tag is processed well in mobile mode, but it displays me "{phocagallery ...}" text "as is" because of PhocaGallery is not installed.

So the only conclusion is it does work on yous site and it doesn't on my. For unknown reason the {mobile}{anything}{/mobile} is not correctly processed on my site, I checked it for other tags as well. But just to confirm it's a plugin issue I did a quick trial:): I put the following tag {mobile}{sdfsdfsdgf}{/mobile} and it doesn't appear on my site (and I should see {sdfsdfsdgf} on the mobile device)

Could you send me ftp credentials to access your website? I'll try to add some debug logging to the plugin.

I'll after 4:00 CET:). Thanks for looking into it
[EDIT] I sent you PM with ftp details. Did you get my email regarding custom work to chenge the code under the home button?