The basic logic is simple: keep a buffer of text read from the file. Try to find a match for the record separator. If we can't find a match, read more text and try again. If we do get a match, then whatever came before the record separator was the record. Stop when you can't match and there's no more data to read into the buffer.
The code is complicated, however, by special cases. When your regular expression matches the empty string, you should get back your data one character at a time. If you find a match for the record separator and have consumed all the data currently in the buffer, you can't be sure that there isn't more of the record separator waiting to be read from the filehandle. So if there's a successful match, you need to put the record and separator back into the buffer, read more data, and try again. And keep trying until you run out of data in the filehandle or you get a match that leaves data in the buffer.
Tom's sanity-checking my code now, but when he's done I'd like to find someone willing (foolish?) to turn it into a CPAN module. I don't have time to do the distro framework, write more tests (I used Test::More when writing the code, and T::M truly rocks), or package it usefully. (I have a stab at a tied filehandle interface so that you can get <FH> even when $RS is a regex).
(you can tell it's a first draft because I bounce around between we and you, one of my weaknesses)