Hi there and welcome to the forums.
The issue of large SharePoint lists is pretty common. Unfortunately, I don't know of an out-of-the-box solution for it. Some people opt for filtering.
For example, say you have customer data. You create two dropdowns: Country and Customer Name. As the user fills out the form, they first select Country, which then filters the Customer Name dropdown to a more managable size. I don't know if this is possible in your data but it's a common option.
The caveat: If you want to filter what is returned from the server, you will have to use a Web Service. SharePoint provides a bunch of Web services, but I'm not sure if they allow filtering on a list, especially server-side. We do this a lot using our Database Accelerator. We filter the contents from SharePoint and/or SQL.
If you want to filter client side, you can do this in InfoPath, but it means your form will still have to load all the records. In which case the performance of the form load will be affected.
As far as the solution you cite, I'm not sure how it was created (I've never seen it), but with code you can achieve a lot! Good luck!