You have hit the most common limitation in SharePoint - lists don't scale beyond ~5000 items.
If you have <5000 items, you can use filtering to return a subset of the results and then use cascading dropdowns to subsequently query the list but the list's default view has to show everything and therein lies the performance issue as you go above several thousand items.
The solution is to move your data into a SQL database and query that. If you have a SQL database on that server, it's easy to set this up with a Web service. Do not use direct pull from the database because it doesn't support parameterized queries. You need a Web service to filter data from SQL (note in ShP you can get around this using filterowssvr) so that you don't pull down the whole kit and caboodle. Qdabra provides a free trial of a Web service to do this or you can write your own.
Best of luck with InfoPath!