Where are files in the Recycle Bin stored, in respect of partitions?

Actually, there is a separate \Recycler directory per partition (C:, D:, etc.). So it stays on the same partition/drive.

Here is a screenshot from two drives on the same computer.

I can now confirm that the behavior is the same when there is only one drive, and multiple partitions.

However, when you open the Recycle Bin icon on your desktop, you see a compilation of all the Recycler folders that are associated with your accounts for convenience.

Based on your question below, what seems to happen is that when you delete something, the file does stay on the actual drive, as previously mentioned. What also happens is that the file is given a random name (my original file was test.txt, but renamed De4.txt on the drive when I searched at a command prompt), and that file is what is entered into that INFO2 file and is passed on to Explorer as you saw it. This is so you only need one Recycle bin can find deleted files, regardless of what drive you are on. What you REALLY see when you do a search a command line, shows that it is not really on both drives. Check out this screenshot:

If I delete a file on drive D, does the file stay on drive D in the Recycle Bin, or is it moved to a centralised Recycle Bin area on drive C?

Each file you delete stays on the drive the file came from. This is why you can set the maximum recycle bin size on a per-size basis (just right-click on the Recycle Bin and go to Properties, and you can change it on a per-drive basis).

Logically, the files themselves are not modified, but rather the master file table is updated and the file is "moved" into the Recycle Bin first. Once you empty the bin, the file is marked as deleted (and just overwritten the next time the drive tries to write a file and needs that space).

When viewing the RECYCLER folder on a partition it shows the contents of the Recycle Bin from all partitions.

Yes, this is the default behaviour on Windows. On each drive, there is a RECYCLER folder (marked as both hidden and system). The Windows Recycle Bin seeks through all local drives and obtains all Recycler entries when you open the bin.

Finally, every time you delete a file, they are placed into a random folder. While that folder exists on all RECYCLER folders on all mounted hard drives (to prevent name collisions), the deleted file only exists on the drive it came from.