[ksooo]

I have been seeing the same thing for a long while. It doesn't bother me because I schedule via the web interface. It bothers my wife but she puts up with it but I put an identical system into my technically challenged parents place and it bothers them, hence i am now looking at it after a long while :-(

@ksooo I have the same situation as OP.

Kodi on mixed clients Windows & Libreelec (PI and x86) to TVH server over wired Gig-E. Scheduling recordings via the TVH webpage works with 100% success rate. Instant recording via the Kodi interface works with anecdotally 50% success rate. I am sure that scheduling guide based recordings in the future work fine as does time-shifting via the Kodi interface. Deleting recordings from Kodi works fine too.

Today I started experimenting trying to localise it.
 

• First thing I did was use a windows Kodi client and deleted the Kodi directory to start fresh - deleted everything in \AppData\Roaming\Kodi\
  
• I then installed the TVH addon, configured it with the server address, username and password only and tested it.
  
• Voila, 100% success rate on instant recordings.
  

Much to my surprise it worked every time.  Note, the process I take is - switch to channel, see video then press the record button on GUI for this test, but usually via the IR remote. In this case time-shifting is enabled but I haven't used the time-shift buffer in Kodi for these tests.

I then compared my old pvr.hts settings.xml file in \AppData\Roaming\Kodi\userdata\addon_data\pvr.hts looking for deltas between my standard configuration. This standard config is set the same on all clients and it is set using the addon GUI in each case.

I found the following diffs in pvr.hts.

Original:
<setting id="autorec_approxtime" default="true">0</setting>
<setting id="pretuner_enabled">true</setting>
<setting id="total_tuners">5</setting>

Fresh:
<setting id="autorec_approxtime">1</setting>
<setting id="pretuner_enabled" default="true">false</setting>
<setting id="total_tuners">2</setting>

I have 6 tuners available.

I changed one line at a time starting with autorec_approxtime. Starting Kodi and then attempting to play, then instant record.  I found that when pretuner_enabled was set to true, it would fail with the usual frequency. If i set it back to false, instant recording would work as expected. I never changed total_tuners in the new file, because pretuner_enabled caused the issue.

The kodi error log says similar error entries as the OP with the "User does not have access" note. The rights for the user are okay many recordings work so I would agree, I don't think access rights are the root of the issue.

2019-08-29 16:07:33.951 T:12824   ERROR: AddOnLog: Tvheadend HTSP Client: pvr.hts - Command addDvrEntry failed: User does not have access
2019-08-29 16:07:33.951 T:12824   ERROR: PVR::CPVRClient::AddTimer: Add-on 'Tvheadend:14.78.3.1:9982' returned an error: server error

I have taken logs from Kodi for Good and for Bad (i.e. when it failed). I have also taken snips of the tvh debug log too.

Process is:

1. Start Kodi
   
2. Switch to ABC (failed on bad log)
   
3. Press instant record
   
4. Stop instant record
   
5. Switch to SBS
   
6. Press instant record (worked on both bad and good log)
   
7. Try record ABC from guide (failed on bad log)
   
8. Exit kodi and copy off log file.
   

I repeated the same for both good and bad.

Good Kodi Log: https://paste.kodi.tv/voxomaxaki.kodi
Good TVH Log: https://paste.kodi.tv/yajatewojo
Good settings.xml: https://paste.kodi.tv/duraxocavi

Bad Kodi Log: https://paste.kodi.tv/ujunatejun.kodi
Bad TVH Log: https://paste.kodi.tv/cexakekowo
Bad settings.xml: https://paste.kodi.tv/fowoviqaja

Kodi Ver : 18.3 Git:20190619-89472b7d69
Tvheadend HTSP Client Ver: 4.4.18
Tvheadend server version: 4.2.8-31~g0a60f73

 @aegidius and @krammcc  if you change the setting in your Kodi addon under Streaming settings "Use predictive tuning to speedup channel switches" from on to off do your instant records start working? If it is already, off then this is a hint only...

Cheers
CV8R

Could you give a recent Kodi 19 nightly build a go? It comes with both, fixes in Kodi core and the tvh addon.