Cannot re-attach SQL Server Express database to the same server after detaching?
Can someone point me to the circumstances that could lead to this problem (database working on the very same server, then detached, not
changed (at least by me), then not being able to re-attach?


You have 2 problems:

Your 'old' server is SQL Server 2008 R2, and the new one is SQL Server 2012.   You cannot attach a database from a SQL Server 2012 instance on a SQL Server 2008R2 instance.
The limit of 10Gbs is exceeded.

What to do:

attach your database to a SQL Server 2012 (or higher) instance.
Export data from  that instance to  your SQL Server 2008 R2 instance.



Is there a way to free up space inside that .mdf file without actually attaching it?


You do not actually need it. I do not know such a way.


Or could it be feasible to take the database I already attached to the new (full) SQL Server, shrink that in size and then attach it to the SQL Server Express instance?  Would attaching the file to a full version of SQL Server change the format of said .mdf file to be unusable by SQL Server Express?


You can do it if you will work on SQL Server 2012 Express.  No - the format will not be changed.