What do I gain if I consider the outcome as ordinal instead of categorical? There are different methods for prediction of ordinal and categorical variables.
What I do not understand, is how this distinction matters. Is there a simple example which can make clear what goes wrong if I drop the order? Under what circumstances does it not matter? For instance, if the independent variables are all categorical/ordinal, too, would there be a difference?
This related question focuses on the type of the independent variables. Here I am asking about outcome variables.
Edit:
I see the point that using the order structure reduces the number of model parameters, but I am still not really convinced.
Here is an example (taken from an introduction to ordered logistic regression where as far as I can see ordinal logistic regression does not perform better than multinomial logistic regression:
library(nnet)
library(MASS)
gradapply <- read.csv(url("http://www.ats.ucla.edu/stat/r/dae/ologit.csv"), colClasses=c("factor", "factor", "factor", "numeric"))

ordered_result <- function() {
  train_rows <- sample(nrow(gradapply), round(nrow(gradapply)*0.9))
  train_data <- gradapply[train_rows,]
  test_data <- gradapply[setdiff(1:nrow(gradapply), train_rows),]
  m <- polr(apply~pared+gpa, data=train_data)
  pred <- predict(m, test_data)
  return(sum(pred==test_data$apply))
}

multinomial_result <- function() {
  train_rows <- sample(nrow(gradapply), round(nrow(gradapply)*0.9))
  train_data <- gradapply[train_rows,]
  test_data <- gradapply[setdiff(1:nrow(gradapply), train_rows),]
  m <- multinom(apply~pared+gpa, data=train_data)
  pred <- predict(m, test_data)
  return(sum(pred==test_data$apply))
}

n <- 100

polr_res <- replicate(n, ordered_result())
multinom_res <- replicate(n, multinomial_result())
boxplot(data.frame(polr=polr_res, multinom=multinom_res))

which shows the distribution of the number of right guesses (out of 40) of both algorithms. 

Edit2: When I use as scoring method the following
return(sum(abs(as.numeric(pred)-as.numeric(test_data$apply)))

and penalize "very wrong" predictions, polr still looks bad, i.e. the plot above does not change very much.
 A: If you ignore the ordered nature of the variables the appropriate methods will still provide correct analysis, but the advantage of using methods for ordered data is they provide greater information about the order and magnitude of significant variables.
A: If you want to model the data and the dependent categorical variable has no ordering (nominal) then you must use a multinomial logit model.  If the dependent variable does have an ordering (ordinal) then you can use a cumulative logit model (proportional odds model).
For me personally, I find the results much easier to interpret for a proportional odds model compared to a multinomial model, especially when you want to report the results to someone not statistically knowledgeable.
These are not the only models you can use but they are very typical.
A: There are major power and precision gains from treating Y as ordinal when appropriate.  This arises from the much lower number of parameters in the model (by a factor of k where k is one less than the number of categories of Y).  There are several ordinal models.  The most commonly used are the proportional odds and continuation ratio ordinal logistic models.
