Have figured out  that it has nothing to do with Verify job. It was all about 
changing the position on the tape. When I tried
mt -f /dev/st0 rewind
and then tried another backup, I got the very same error.

With help of this thread:
http://www.backupcentral.com/phpBB2/two-way-mirrors-of-external-mailing-lists-3/bacula-25/problem-with-fast-forward-space-file-option-130425/?sid=b9c0fff5339e44823882ca6d8f73c862

I've changed my sd config to:
Device {
  Name = TAPE
  Media Type = LTO-4
  Archive Device = /dev/st0
  AutomaticMount = yes
  AlwaysOpen = yes                     # default: no
  Offline On Unmount = no
  Hardware End of Medium = yes         # default: yes
#  BSF at EOM = yes                     # default: no
  Backward Space Record = yes          # default: yes
  Fast Forward Space File = yes        # default: yes
#  TWO EOF = yes                        # default: no
  LabelMedia = yes
}

(BSF at EOM and TWO EOF reverted back to defaults)

And now all work fine.

May help to others too..

+----------------------------------------------------------------------
|This was sent by ogiraz AT kepkur.com DOT tr via Backup Central.
|Forward SPAM to abuse AT backupcentral DOT com.
+----------------------------------------------------------------------



------------------------------------------------------------------------------
Mobile security can be enabling, not merely restricting. Employees who
bring their own devices (BYOD) to work are irked by the imposition of MDM
restrictions. Mobile Device Manager Plus allows you to control only the
apps on BYO-devices by containerizing them, leaving personal data untouched!
https://ad.doubleclick.net/ddm/clk/304595813;131938128;j
_______________________________________________
Bacula-users mailing list
Bacula-users AT lists.sourceforge DOT net
https://lists.sourceforge.net/lists/listinfo/bacula-users