I've deleted hundreds of thousands of old unneeded records and this is increased the unallocated database space by quite a bit but it has of course not increased any free hard drive space.
No, that will only increase the free space in the file
I had hoped SQL Server would use only unallocated space first before using any more new disk space but apparently it is not.
It will do that. It could be that the free space you created is free space on allocated pages, not empty, unallocated pages. SQL can't use free space on a page belonging to tableX for tableY. You probably need to rebuild indexes to see that free space made available to the rest of the DB.
Don't shrink, you want free space in your database to let SQL reuse that free space. That's not what shrink does.
Microsoft Certified Master: SQL Server, MVP, M.Sc (Comp Sci)SQL In The Wild
: Discussions on DB performance with occasional diversions into recoverability
We walk in the dark places no others will enter
We stand on the bridge and no one may pass