In the Exchange space there are definitely problems. Since this is
based on the same store, I would not be comfortable doing this. There
is a command line application that will let you backup  to a file, or you
can get the add-on agent for Veritas or some other third party product.

Backing up the M drive  is not a supported scenario, nor will it provide
you a recoverable set of data.

This is absolutely correct. MS advises not to do anything via the M
share which is why is not mapped by default. If you attempt a backup  via
the M drive  chances are you will not every restore it. MSDMBack is the
command line util that will backup and restore SPS. You can create a
script file that can be called via the scheduler and automate it to some
degree.

I know that to backup  SPS I need to use the script msdmback.vbs and I'm
doing that already; but as you know msdmback doesn't let you restore a
single file or folder but only the whole SPS server.
I'm often asked to restore some files or folders unintentionally deleted.
I've install the undeleted web part for restoring a single file but the only
way to restore deleted folders is doing a full restore of SPS server and
very likely someone will lose his/her freshly updated files.
I was wondering if doing a backup of drive  M could help me accomplish the
task of restoring folders.
I've seen that the only way to backup drive M is from network (I tried to
backup M locally but without success). I scheduled a nightly and a lunch
time backup of M, but they often go wrong, I mean the nightly job is still
running when the other one starts, and as a result, both of the backup files
are unusable.
Does anyone know what could cause that problem?

I am not sure if you will ever get a useable backup  from M drive. There
are a couple of things you can do to restore a single file. First use
the undelete tool which you are doing. Second, keep an offline server
available ( does not have to be a big server ) and do a full restore
back to that server and then copy the file you want to the prod server.
Another possibility is to check some of these 3rd party management tools
or backup solutions. Some of them tout single file restores.

http://www.sharepointserver.com/backup.html