Which seems to find proper result on first use, but on subsequent searches it seems to find invalid positions, is there something I'm doing wrong, or is there a better way?
No, grep (or fgrep) would probably be faster. There are incredibly clever algorithms for searching for one string inside another. The larger the search string, the faster they go.
You should be limited only by the speed of your disks. In other words. you should be able to search the data as fast as you can read it from the disk drive.