As Maddox stated, the search widget and APIs are notoriously hard to work with and very inflexible.
I agree it would be nice to be able to search recorded shows and movies, but that does not mean it's easy to implement. The dvr backend search feature only includes upcoming guide data. We are planning to upgrade the search backend in the future to allow for additional features.