Where is recycle bin actually stored?

In the file system itself, the Recycle Bin is just a hidden folder, and is "almost" like a regular folder.

See here: Where is recycle bin actually stored

 C:\$Recycle.Bin

That's a good question.  Was it working correctly previously?

I assume this is just a regular file on your C: hard drive?  Or is it something else?

I haven't seen it often, but the recycle bin can be reset if it's not acting right.  See: http://www.tech-recipes.com/rx/4316/windows-7-how-to-reset-the-recycle-bin/

Sorry for being so dense, but are you describing Windows 10?

I have an external drive.  Will the deleted files show up in the C drive recycle bin?  Right now nothing does.

It's the same on Windows NT/2000 all the way up to XP/Vista/7/8/10.

When you delete a file on an external drive, it won't move the file to your internal drive (it won't move it to the C:\$Recycle.Bin folder).  But if you've enabled recycling on the external drive, it should move to the $Recycle.Bin folder on the external drive itself (so something like F:\$Recycle.Bin for example).  When you open your recycle bin icon, it should list files in the recycling folder of every connected hard drive (all in one combined view/list).

You can decide if recycling is allowed on an external drive by right-clicking your Recycle Bin and choosing Properties.

If it's setup to recycle on that drive but still not showing up in the recycle bin, I'd go ahead and reset the Recycle Bin (same instructions as linked above, just do it on your external drive).