In which places in China can travellers not stay at just any random local hotel?

Some of it comes down to the hotel chain.

For example Hanting ?? at most can accept foreigners. Sometimes if they do, they have some weird policy about no free breakfast or something. However some can not ???? receive foreign guests.

?? Home Inn, is hit or miss in mainland cities. Some take you, some don't. Best to call ahead of time and ask in Chinese ???????? néng bù néng ji?dài wàib?n?

The final one is JinJiangInn ???? and they pretty much always are able to accommodate foreign guests.

Because foreign guests in some cities are so few, it may not be worth it for the hotel chain (or branch) to do all this paperwork and register with the local police to be accredited to accept foreigners just for the 4 foreigners who roll in each year.

Best are the YHA hostels, they have a great app and a booklet if you are into that kinda thing. Get the membership card if you are a frequent backpackers or suitcaser. However, be on the lookout for the 'sham' YHA hostels (with an orangeish YHA looking logo) because we know everything in China can be '??' copycatted.

Usually rooms run 150 RMB plus per night for a standard double

There is no state level law that to regulate the foreigners to stay in special hotels.

According to §39 Foreigners Entry and Exit Management Law of PRC, the hotels must register the foreign guests according to "regulations which are applied" and report the registration to local police authority.

The "regulations which are applied" could be made by any local authorities. Thus different cities have different regulations. Commonly, foreigners need to stay in a shè-wài hotel.

Peking and Shanghai local government officially cancelled the regulation, which means foreigners can stay in any hotels or hostels in Peking and Shanghai.

If you travel to other places, either to ask the hotel in advance or book a shè-wài hotel.

There has never really been codified law on whether hotels can take foreigners, in China. The law requires hotels to report foreigners to the local police authority, period, but local governments might have their own rules (which are almost always not made public, this being China). Some hotels simply do not want to go through this hassle, and some hotels might be prohibited from doing so by local authorities.

The major, Ministry of Commerce star-rated hotels almost always take foreigners (because that's exactly what the MoC star rating system is intended for), but smaller, unrated hotels often cannot. I've seen a lot of business hotels/motel sort of place that do not take foreigners. A acquaintance of Japanese nationality (who has lived in China since forever), for instance, always encounters problems when she goes out with friends: they forget about the fact that she isn't a Chinese citizen all of the time! And, that's not just for remote places: this happens frequently even in large cities like Beijing, Shanghai, and Shenzhen.

There was even once when I checked into a hotel using my Hong Kong/Macao Visit Permit (as I was arriving directly from Hong Kong), and the hotel staff hesitated to take that until I repeatedly assured them I'm a mainland Chinese resident, and after they apparently called their supervisor (or perhaps the local police authority). Many places just would just outright reject identification other than the Mainland Chinese ID.

So, your options might be significant limited no matter where you travel. Moreover, there's not even a simple answer to this question. A rule of thumb would be to stay in the largest of the hotels, and those of which are apparently rated above three stars. Also, try to find hotels which are clearly owned/operated by an international corporation (such as Sheraton, Novotel and Hilton), or a "state guest house" operated by the government (such as the Friendship Hotel Beijing ??????, or the Wuzhou Guest House ???? in Shenzhen). I can hardly imagine that any of them would reject foreign guests.

I was initially told I could not stay at the Wuzhishan Yatai Resort in Hainan, just over a month ago. This is a VERY nice mountain resort, and part of a big chain. My Chinese gf booked the hotel online, but when we showed up at the gate they tried to turn us away when they saw my white face. We heard later that there is a missile base nearby, and about a year ago a British tourist was lost for a few days in the woods. When he was found there was some concern he was a spy, embassies were involved, etc. So after that they started booking only mainland Chinese. We were also told that they look the other way when Koreans or Japanese show up.

We had driven five hours, the last two over half-finished, sometimes unpaved, dangerous mountain roads. When I heard this I started using English vocabulary most Chinese know but seldom hear. They eventually let me stay after I signed a paper stating that I would not wander around the grounds, except in the company of a hotel employee. It seems like a ridiculous prohibition to me. It really is a fabulous resort. We paid about 300 yuan per night. I am sure in the US it would be $300 to $400. Once we got in, we enjoyed every minute, except that the hotel employee turned us back before reaching the summit because he was running out of time. I am also sure that the CIA and the NSA know everything about the base. I am also sure that they have spies with PRC passports. Would forbidding foreigners from staying in hotels in Los Alamos make us any safer? Of course not. But this is politics and "policy", which means that rational arguments rarely come into play.

I still need to find a way to get to the top of Wuzhishan, mostly because they told me "no".

There are several wards in China that you won't be able to visit unless you've been invited by the government, Lushunkou is one example. Typically they are neighborhoods, towns, cities, etc. where they have military installations, or other sensitive regions. In these areas you won't be able to stay in a hotel, which might not be confirmed until they check with the police.

They're the equivalent of those military family neighborhoods you would find in the west — where they have giant signs saying you can be pulled over for inspection at any time.

One such area is Shilin Town in the Shilin Yi Autonomous County just east of Kunming in Yunnan where the stone forest tourist attraction is located.

I turned up there a few months ago while hitchhiking out of Kunming thinking I would have plenty of time to find a cheap hotel in a place that size before it got dark.

I went to five or six places and all said I couldn't stay, some not until asking for my ID card and seeing I only had a passport. Then I met a Chinese guy who took me to another half dozen places and did the talking for me, even going to fancier places outside my price range.

It turns out only one hotel, part of the conference centre, is allowed to have foreigners stay, and it was several times my budget.

We couldn't discern the exact reason it wasn't allowed but it seemed to be that it was an official rule that if broken would likely involve imprisonment for the hotel person! This is why people didn't want to bend the rule in this area even though I'd been in other areas where people occasionally bent the rules even to the extent of not wanting to see my passport.

Sadly I forget some of the details and don't have a way to contact the local guy who helped me. I ended up staying in his spare room, which is very rare in China.

There are to my information no special provinces where you do not need to be registered as a foreigner to stay overnight, or cannot stay at all. Every hotel has to register you with the police so you can stay there. The question is if they have that system.

So the question is a hotel-by-hotel one, not a question which region you stay in.