Where does Koha say the record is "Lost or missing?" On the screen where you place the hold?
It says it in the OPAC view when I log in (perhaps I should log in as a non-admin user?). I have uploaded a screenshot here: http://intknowledge.com/sites/default/files/u8/missing-cannotHoldItem.png ... I made a patron-user without admin rights and that user got the same message, so _somewhere_ there is a hold on that item.
Admin rights don't affect users of the OPAC. One is either a valid logged-in patron or not. Logged-in "superlibrarian" patrons, for instance, don't gain any additional privileges in the OPAC. It sounds to me like something in your setup is limiting the number of holds possible. I'm not sure about your version.... Do you have a "maxreserves" setting in system preferences? Do you have a "holds allowed" option under Administration -> Circulation and fines rules? -- Owen -- Web Developer Athens County Public Libraries http://www.myacpl.org