Both should be correct, but without the 的 is more natural, I believe. They are both accepted now.

Should be acceptable.

In the different Chinese languanges you see subjects in different places of the sentence construction that are equally acceptable. This is one example.

I was wondering if that would work too.

it translates more to "booke a place" I guess...

订 in itself means to book
位 means a seat / seats
Many words in Chinese are formed in this way including a verb and a noun at the same time for elaboration. Often this kind of words can be used both as a verb and as a noun (a similar application as a gerund).
e.g. 骑马 Ride + Horse

However, it would be a little bit tricky to add adverbs and adjectives to such phrases and stay natural. Please acknowledge it first and move on.

订位 is selfexplaining and includes an object in this case as you only can use it when you reserve a table or a seat.

订位 is selfexplaining in this case and includes the object here as you can only use this verb when you book a seat or reserve a table.