I have finally found nitrate, by doing something I wanted to avoid: cheating. But there seems to be no other way.
So, here is my almost-legit guide to finding nitrate (or any other resource). Hopefully it can help people who have the same problems I had.
1. open the file blocks.xml (make a copy of the original first) and find the comment line saying "ore block visualisation. Uncomment this section to make ore visible".
Do what it says: uncomment the entire section. This is key because it will show you where the ore is when flying underground.
(In case you're not familiar with editing XML: add "-->" to the end of the first line of the block to make it look like this:
"<!-- ore block visualisation start. uncooment this section to make underground ore visible. -->"
Then add "<!--" to the beginning of the last line of the block to make it look like this:
"<!-- ore block visualisation end -->"
This way, only those two lines remain comments and the lines in-between are now active. Or, you could simply delete both lines..)
2. start the game, open the console with F1 and enter "debugmenu on". This will give you an additional menu in the pause screen.
3. in the debug menu, check "fly mode" and "no collision". This will allow you to fly both above and below the surface. You ascend with the <space> key and descend with the key for crouch (not toggle crouch! usually <C>

.
4. fly around and descend below the surface level. Because of the blocks.xml edit, you will see the ore blocks. Fly around until you find the ore you're looking for, and put a marker on the map for later reference.
5. exit the game, and copy the original version of the blocks.xml back in order to hide the underground ore again. This is necessary because as long as it is visible, mining is messed up for some reason (in my case, hitting nitrate yields glass).
I find it helpful to keep two copies of the original and edited version of the file, so I can quickly change it back and forth.
6. enter the game again, go to your marked spot, get out the auger, and mine away.
This way, I found a large deposit of nitrate in a few seconds. It was NOT in the snow biome, and it was NOT near any boulders either. Instead it was in the forest south of the farm. I mined 5000+ nitrate in no time and haven't even mined half of it yet.
I could also confirm that there are even larger deposits in the snow biome, but they are few and far between. Finding them without taking a look underground is pretty much like playing the lottery.
So, thanks to the devs for leaving the debug tools accessible! They saved my game. It's cheating but still better than quitting the game.