toonski,
I see that you have been at the Monastery a while, but haven't done a lot of posting. It might be helpful to spend some time on how reading the site
FAQ for pointers on how to ask a question effectively. Without any code, it is almost impossible to help you. Some questions for you:
Are you using pack/unpack correctly to ensure your fixed length records are always of the correct length?
Is there a reason you can't use a DBM module or is there a specific reason for the flat file fixed length records?
Are you using open, seek, and tell to find record locations or sysopen, sysread, and sysseek
More than likely, you can get away with the CPAN module I listed above, but if you want to do a flat file fixed length database, please provide your code.
Cheers - L~R
Update: How is it when you start to post to a reply, no one else has done so, but by the time you click submit - 6 other monks have provided better solutions before you? I would still like to see the code even if Jeffa's crystal ball idea was spot on - it will help other monks on their journey.