So I guessed that if I made them extend RemoteException then I would have solved my problem.
That's simply a bad design! You should only use inheritance if you have an IS-A relationship between 2 classes, not because it's convenient. And because RecordNotFoundException is not a RemoteException using inheritance is not the way to go.
Maybe I am wrong on that one?
Just create an own business service interface where each method throws RemoteException. Here you decide between a thick or thin client approach.
Here you'll find more info about the do's and don'ts about RMI (& RemoteException).