I do not have the answer for you, but if i had your problem, then i would try to identify the cause through benchmarking the code with Devel::NYTProf.
Seeing which line of code consumes most time, might help you in identifying the root cause, and as such fixing it.
Some random thought based on your description (might not apply):
"Perl takes several seconds may return no rows, even where there are matching candidates."
From the behaviour this makes me think of a locking/timeout issue. E.g. the file is locked through another process, and your call times out, while trying to acquire a lock. Googling i stumbled across http://blogs.perl.org/users/timm_murray/2013/02/sqlite-and-writes.html
which mentions locking in combination with sqlite_busy_timeout. One thing contradicting this theory however is, that you use
RaiseError => 1
, and as such you should get an exception when you fail to acquire the lock. An empty result, where there should be a result, is however many times the symptom of an unhandled exception or timeout.
Googling further i also stumbled over the following article http://beets.io/blog/sqlite-nightmare.html
which mentions that in certain circumstances sqlite might sleep for whole seconds instead of microseconds when trying to acquire a lock. If you have concurrent processes/threads accessing the same sqlite file, then this might be another possible theory.
Can you reproduce your issue with a copy of the sqlite database, with no other process accessing the file?