I've built a dedicated server applications that ships with the application. As of now it is storing data in a mix of binary- and xml files, but I've found that this gets way too messy and slow now that the amount of data required to store grows continously.
So what are my options for storing data in a format that is easier search/editable. Being able to do SQL queries on the data would be preferable, but I don't want to force the users into installing a database system.
I believe you are looking for SQL Server Compact.
You can easily implement all of the support files into your installation, it's free, has great support in .NET, and has a small footprint. It's a great alternative to what you are using now. Of course, there are a few downsides, such as lack of stored procedure support and a little bit of extra work while trying to use LINQ, but those shouldn't be big problems for you.
Your other alternative is something like SQLite. SQLite is fast and portable (Google Chrome uses it), and usable in .NET, but has poor support for date/time manipulation, and a slew of other similar inconveniences.