I also had this problem but only with certain songs. I could not determine why OpenLP did not match the songs in the service with the already-existing song in the database.
If you don't need the feature of automatically adding new songs to the list (which is only useful if someone else sets up the service and sends you it) then you can turn off the option "Import Missing Songs from Service Files" in the Songs tab of the settings window which stops the problem.