How would I list all entries regardless of section or structure? I'm trying to build and XML site map that sorts all entries by their modification dates with the newly modified first. 

{% for entry in craft.entries.find() %} ignores the structures,

{% for entry in craft.entries.section().find() %} returns the same as above,

{% for entry in craft.entries.section('mainPages').find() %} returns the structure as expected.

Looking for a way to include everything in a single, sortable query.
Actually your code should work just fine. But by default only 100 entries are fetched, maybe you need to increase the limit:

{% set entries = craft.entries.section().limit(null) %}


But if you just want to create a Sitemap, try Ben Croker's Sitemap-Plugin (I really like it)